Source code for submission s1003

fm.cpp

  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6. #include <numeric>
  7. #include <utility>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <string>
  15. #include <queue>
  16.  
  17. #define vi vector <int>
  18. #define vl vector <long long>
  19. #define vpii vector <pair <int,int> >
  20. #define mp(x,y) make_pair(x,y)
  21. #define all(x) (x).begin(),(x).end()
  22. #define sz(x) (int)(x).size()
  23. #define FOR(i,n) for(ll i=0;i<int(n);i++)
  24. #define READ(v,n) {FOR(i,n){ll x;cin>>x;v.pb(x);} }
  25. #define gmin(a,b) {if (b<a) a=b;}
  26. #define gmax(a,b) {if (b>a) a=b;}
  27. #define pb push_back
  28. #define ppb pop_back
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. using namespace std;
  32.  
  33. int getxy(long* arr, int x, int y) {
  34.   if (x < 0 || y< 0) return 0;
  35.   return arr[x*1500 + y];
  36. }
  37.  
  38.  
  39. long a[1500*1500];
  40. long b[1500*1500];
  41.  
  42. int main(){  
  43.   int ar,ac,tr,tc;
  44.   while (cin>>ar>>ac>>tr>>tc) {
  45.     for (int i=0; i < 1500*1500; ++i){
  46.       a[i] = 0; b[i] = 0;
  47.     }
  48.     string s;
  49.     for (int i=0; i<ar+tr; ++i) {
  50.       if (i >= ar) {
  51.         for (int j=0; j<ac+tc; ++j) {
  52.           a[1500*i + j] = getxy(a, i-1, j) + getxy(a, i, j-1) - getxy(a, (i-1), j-1);
  53.         }
  54.       } else {
  55.         cin >> s;
  56.         for (int j=0; j<ac+tc; ++j) {
  57.           if (j >= ac) {
  58.             a[1500*i + j] = getxy(a, i-1, j) + getxy(a, i, j-1) - getxy(a, (i-1), j-1);
  59.           } else
  60.           if (s[j] == '.') {
  61.             a[1500*i + j] = getxy(a, i-1, j) + getxy(a, i, j-1) - getxy(a, (i-1), j-1);
  62.           } else {
  63.             a[1500*i + j] = getxy(a, i-1, j) + getxy(a, i, j-1) - getxy(a, (i-1), j-1) + 1;
  64.           }
  65.         }
  66.       }
  67.     }
  68.     for (int i=0; i<ar+tr; ++i) {
  69.       for (int j=0; j<ac+tc; ++j) {
  70.         b[1500*i + j] = getxy(b, i-tr, j) + getxy(b, i, j-tc) - getxy(b, (i-tr), j-tc);
  71.         if ((getxy(a, i, j) - getxy(a, i-tr, j) - getxy(a, i, j-tc) + getxy(a, (i-tr), j-tc)) > 0) ++b[1500*i + j];
  72.  
  73.         //cout << b[1500 * i + j] << " ";
  74.       }
  75.       //cout << endl;
  76.     }
  77.     long m = getxy(b, ar, ac);
  78.     for (int i = 0; i < tr; ++i) {
  79.       for (int j = 0; j < tc; ++j) {
  80.         //if (i <= ar && j <= ac)
  81.           if ((getxy(b, ar+i, ac+j) < m)) m = (getxy(b, ar+i, ac+j));
  82.       }
  83.     }
  84.     cout << m<<endl;
  85.   }
  86.  
  87.   return 0;
  88. }
  89.  
  90.  
  91.