Guest User

Untitled

a guest
Jun 17th, 2015
387
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <fstream>
  4. #include <iomanip>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. #include <queue>
  9. #include <stack>
  10. #include <set>
  11. #include <map>
  12. #include <list>
  13. #include <vector>
  14. #include <string>
  15. #include <cstring>
  16. #include <cmath>
  17. #include <ctime>
  18. #include <cassert>
  19. #include <bitset>
  20.  
  21. using namespace std;
  22.  
  23. #define forn(i, n) for(int i = 0; i < (int)(n); i++)
  24. #define forn1(i, n) for(int i = 1; i <= (int)(n); i++)
  25. #define all(a) (a).begin(), (a).end()
  26. #define sz(a) (int)((a).size())
  27. #define mp make_pair
  28. #define pb push_back
  29. #define X first
  30. #define Y second
  31. #define x first
  32. #define y second
  33. #define y1 __y1
  34. #define sqr(x) ((x) * (x))
  35.  
  36. typedef long long li;
  37. typedef long double ld;
  38. typedef pair<li, li> pt;
  39.  
  40. const int INF = (int)(1e9);
  41. const li INF64 = (li)(INF) * (li)(INF);
  42. const ld eps = 3e-8;
  43. const ld pi = ld(3.1415926535897932384626433832795);
  44.  
  45. bool in(int i, int j, int n, int m)
  46. {
  47.     return i >= 1 && i <= n && j >= 1 && j <= m;
  48. }
  49.  
  50. inline int myrand()
  51. {
  52.     return (rand() ^ (rand() << 15));
  53. }
  54.  
  55. const int dx[] = {-1, 0, 1, 0};
  56. const int dy[] = {0, 1, 0, -1};
  57.  
  58. const int N = 1001;
  59.  
  60. short a[N][N];
  61. int sum[N][N];
  62. int n, m;
  63. int A, B, C, D;
  64. short aa[N][N];
  65.  
  66. inline bool read()
  67. {
  68.     if(scanf("%d %d", &m, &n) != 2)
  69.         return false;
  70.  
  71.     assert(scanf("%d %d %d %d", &A, &B, &C, &D) == 4);
  72.     swap(A, B);
  73.     swap(C, D);
  74.  
  75.     forn1(i, n)
  76.     {
  77.         forn1(j, m)
  78.         {
  79.             assert(scanf("%d", &a[i][j]) == 1);
  80.         }
  81.     }
  82.  
  83.     return true;
  84. }
  85.  
  86. const int LOG = 10;
  87. short Min[N][N][LOG];
  88. int pow2[N], lg2[N];
  89.  
  90. inline void buildMin()
  91. {
  92.     pow2[0] = 1;
  93.     for(int i = 1; i < N; i++)
  94.     {
  95.         pow2[i] = pow2[i - 1] * 2;
  96.     }
  97.  
  98.     for(int i = 1; i < N; i++)
  99.     {
  100.         int res = 0, cur = 1;
  101.         while(cur <= i)
  102.         {
  103.             cur *= 2;
  104.             res++;
  105.         }
  106.  
  107.         lg2[i] = res - 1;
  108.     }
  109.  
  110.     forn1(j, m)
  111.     {
  112.         forn(pow, LOG)
  113.         {
  114.             forn1(i, n)
  115.             {
  116.                 if(pow == 0)
  117.                 {
  118.                     Min[j][i][pow] = aa[i][j];
  119.                 }
  120.                 else
  121.                 {
  122.                     if(i + pow2[pow] - 1 <= n)
  123.                     {
  124.                         Min[j][i][pow] = min(Min[j][i][pow - 1], Min[j][i + pow2[pow - 1]][pow - 1]);
  125.                     }
  126.                 }
  127.             }
  128.         }
  129.     }
  130.  
  131.     return;
  132. }
  133.  
  134. inline int getMin(int idx, int lf, int rg)
  135. {
  136.     int len = rg - lf + 1;
  137.     return min(Min[idx][lf][lg2[len]], Min[idx][rg - pow2[lg2[len]] + 1][lg2[len]]);
  138. }
  139.  
  140. inline int getSum(int i1, int j1, int i2, int j2)
  141. {
  142.     return sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
  143. }
  144.  
  145. int b[N];
  146.  
  147. inline int solve(pt &res)
  148. {
  149.     int ans = -1;
  150.  
  151.     forn1(ii, n)
  152.     {
  153.         if(ii + A - 1 > n)
  154.             continue;
  155.         forn1(j, m)
  156.         {
  157.             b[j] = getMin(j, ii + 1, ii + A - 1 - C);
  158.         }
  159.  
  160.         multiset<int> S;
  161.  
  162.         int last = -1;
  163.  
  164.         for(int j = 2; j < B; j++)
  165.         {
  166.             int jj = j + D - 1;
  167.             if(jj >= B)
  168.                 break;
  169.             S.insert(b[j]);
  170.             last = j;
  171.         }
  172.  
  173.         int init = getSum(ii, 1, ii + A - 1, B);
  174.         init -= *S.begin();
  175.  
  176.         if(init >= ans)
  177.         {
  178.             ans = init;
  179.             res = mp(ii, 1);
  180.         }
  181.  
  182.         int ins = 2;
  183.  
  184.         for(int j = B + 1; j <= m; j++)
  185.         {
  186.             S.insert(b[++last]);
  187.             S.erase(S.find(b[ins++]));
  188.             int cur = getSum(ii, j - B + 1, ii + A - 1, j) - *S.begin();
  189.             if(cur >= ans)
  190.             {
  191.                 ans = cur;
  192.                 res = mp(ii, j - B + 1);
  193.             }
  194.         }
  195.     }
  196.  
  197.     return ans;
  198. }
  199.  
  200. inline void solve()
  201. {
  202.     forn1(i, n)
  203.     {
  204.         int s = 0;
  205.         forn1(j, m)
  206.         {
  207.             s += a[i][j];
  208.             sum[i][j] = sum[i - 1][j] + s;
  209.         }
  210.     }
  211.  
  212.     forn1(i, n)
  213.     {
  214.         forn1(j, m)
  215.         {
  216.             if(i + C - 1 > n || j + D - 1 > m)
  217.                 continue;
  218.             aa[i][j] = getSum(i, j, i + C - 1, j + D - 1);
  219.         }
  220.     }
  221.  
  222.     buildMin();
  223.  
  224.     pt res1 = mp(0, 0);
  225.     int ans = solve(res1);
  226.  
  227.     pt res2 = mp(0, 0);
  228.     int mn = INF;
  229.  
  230.     for(int i = res1.x + 1; i <= res1.x + A - 1; i++)
  231.     {
  232.         for(int j = res1.y + 1; j <= res1.y + B - 1; j++)
  233.         {
  234.             if(i + C - 1 >= res1.x + A - 1 || j + D - 1 >= res1.y + B - 1)
  235.                 continue;
  236.             int cur = getSum(i, j, i + C - 1, j + D - 1);
  237.             if(cur < mn)
  238.             {
  239.                 mn = cur;
  240.                 res2 = mp(i, j);
  241.             }
  242.         }
  243.     }
  244.  
  245.     swap(res1.x, res1.y);
  246.     swap(res2.x, res2.y);
  247.     cout << res1.x << ' ' << res1.y << endl;
  248.     cout << res2.x << ' ' << res2.y << endl;
  249.     return;
  250. }
  251.  
  252. int main() {
  253. #ifdef _DEBUG
  254.     assert(freopen("input.txt", "rt", stdin));
  255.     assert(freopen("output.txt", "wt", stdout));
  256. #endif
  257.  
  258.     cout << setprecision(10) << fixed;
  259.     cerr << setprecision(10) << fixed;
  260.  
  261.     srand(int(time(NULL)));
  262.  
  263.     assert(read());
  264.     solve();
  265.  
  266. #ifdef _DEBUG
  267.     cerr << "TIME == " << clock() << " ms" << endl;
  268. #endif
  269.     return 0;
  270. }
Advertisement
Add Comment
Please, Sign In to add comment