Guest User

Untitled

a guest
Jun 17th, 2015
369
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.55 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 = 1111;
  59.  
  60. int a[N][N], sum[N][N];
  61. int n, m;
  62. int A, B, C, D;
  63. int aa[N][N];
  64.  
  65. inline void gen()
  66. {
  67.     n = m = 100;
  68.     forn1(i, n)
  69.     {
  70.         forn1(j, m)
  71.         {
  72.             a[i][j] = rand() % 100 + 1;
  73.         }
  74.     }
  75.  
  76.     A = rand() % n + 1;
  77.     while(A <= 10)
  78.         A = rand() % n + 1;
  79.     B = rand() % m + 1;
  80.     while(B <= 10)
  81.         B = rand() % m + 1;
  82.     C = rand() % (A - 2) + 1;
  83.     D = rand() % (B - 2) + 1;
  84.     return;
  85. }
  86.  
  87. inline bool read()
  88. {
  89.     //gen();
  90.     //return true;
  91.     if(scanf("%d %d", &m, &n) != 2)
  92.         return false;
  93.  
  94.     assert(scanf("%d %d %d %d", &A, &B, &C, &D) == 4);
  95.     swap(A, B);
  96.     swap(C, D);
  97.  
  98.     forn1(i, n)
  99.     {
  100.         forn1(j, m)
  101.         {
  102.             assert(scanf("%d", &a[i][j]) == 1);
  103.         }
  104.     }
  105.  
  106.     return true;
  107. }
  108.  
  109. const int LOG = 12;
  110. int Min[N][N][LOG];
  111. int pow2[N], lg2[N];
  112.  
  113. inline void buildMin()
  114. {
  115.     pow2[0] = 1;
  116.     for(int i = 1; i < N; i++)
  117.     {
  118.         pow2[i] = pow2[i - 1] * 2;
  119.     }
  120.  
  121.     for(int i = 1; i < N; i++)
  122.     {
  123.         int res = 0, cur = 1;
  124.         while(cur <= i)
  125.         {
  126.             cur *= 2;
  127.             res++;
  128.         }
  129.  
  130.         lg2[i] = res - 1;
  131.     }
  132.  
  133.     forn1(j, m)
  134.     {
  135.         forn(pow, LOG)
  136.         {
  137.             forn1(i, n)
  138.             {
  139.                 if(pow == 0)
  140.                 {
  141.                     Min[j][i][pow] = aa[i][j];
  142.                 }
  143.                 else
  144.                 {
  145.                     if(i + pow2[pow] - 1 <= n)
  146.                     {
  147.                         Min[j][i][pow] = min(Min[j][i][pow - 1], Min[j][i + pow2[pow - 1]][pow - 1]);
  148.                     }
  149.                 }
  150.             }
  151.         }
  152.     }
  153.  
  154.     return;
  155. }
  156.  
  157. inline int getMin(int idx, int lf, int rg)
  158. {
  159.     assert(rg >= lf);
  160.     int len = rg - lf + 1;
  161.     return min(Min[idx][lf][lg2[len]], Min[idx][rg - pow2[lg2[len]] + 1][lg2[len]]);
  162. }
  163.  
  164. inline int getSum(int i1, int j1, int i2, int j2)
  165. {
  166.     if(!(i2 >= i1 && j2 >= j1))
  167.     {
  168.         cerr << i1 << ' ' << i2 << ' ' << j1 << ' ' << j2 << endl;
  169.         assert(false);
  170.     }
  171.  
  172.     return sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
  173. }
  174.  
  175. inline int naive()
  176. {
  177.     int res = -1;
  178.  
  179.     forn1(i, n)
  180.     {
  181.         forn1(j, m)
  182.         {
  183.             int i2 = i + A - 1, j2 = j + B - 1;
  184.             if(i2 > n || j2 > m)
  185.                 continue;
  186.             int cur = getSum(i, j, i2, j2);
  187.             //cerr << "i j sum == " << i << ' ' << j << ' ' << cur << endl;
  188.             //cerr << i2 << ' ' << j2 << endl;
  189.             int mn = INF;
  190.             for(int ii = i + 1; ii <= i2 - 1; ii++)
  191.             {
  192.                 for(int jj = j + 1; jj <= j2 - 1; jj++)
  193.                 {
  194.                     int ii2 = ii + C - 1, jj2 = jj + D - 1;
  195.                     if(ii2 >= i2 || jj2 >= j2)
  196.                         continue;
  197.                     mn = min(mn, getSum(ii, jj, ii2, jj2));
  198.                 }
  199.             }
  200.  
  201.             res = max(res, cur - mn);
  202.         }
  203.     }
  204.  
  205.     assert(res >= 0);
  206.     return res;
  207. }
  208.  
  209. int b[N];
  210.  
  211. inline int solve(pt &res)
  212. {
  213.     int ans = -1;
  214.  
  215.     forn1(ii, n)
  216.     {
  217.         if(ii + A - 1 > n)
  218.             continue;
  219.         forn1(j, m)
  220.         {
  221.             b[j] = getMin(j, ii + 1, ii + A - 1 - C);
  222.         }
  223.  
  224.         //cerr << "B == " << endl;
  225.         //forn1(j, m)
  226.         //  cerr << b[j] << ' ';
  227.         //cerr << endl;
  228.  
  229.         multiset<int> S;
  230.  
  231.  
  232.         //cerr << "i == " << ii << endl;
  233.         int last = -1;
  234.  
  235.         for(int j = 2; j < B; j++)
  236.         {
  237.             int jj = j + D - 1;
  238.             //cerr << "jj == " << j << ' ' << jj << endl;
  239.             if(jj >= B)
  240.                 break;
  241.             S.insert(b[j]);
  242.             last = j;
  243.         }
  244.  
  245.         assert(last >= 1);
  246.  
  247.         int init = getSum(ii, 1, ii + A - 1, B);
  248.         //cerr << "initsum == " << init << endl;
  249.         //cerr << "initMin == " << *S.begin() << endl;
  250.         init -= *S.begin();
  251.  
  252.         if(init >= ans)
  253.         {
  254.             //cerr << "INIT == "<< init << endl;
  255.             ans = init;
  256.             res = mp(ii, 1);
  257.         }
  258.  
  259.         //cerr << "szs == " << sz(S) << endl;
  260.         int ins = 2;
  261.  
  262.         for(int j = B + 1; j <= m; j++)
  263.         {
  264.             //cerr << "SZS == " << sz(S) << endl;
  265.             //for(multiset<int>::iterator it = S.begin(); it != S.end(); it++)
  266.             //  cerr << *it << ' ';
  267.             //cerr << endl;
  268.             //cerr << "j == " << j << endl;
  269.             //cerr << "insert == " << b[j - 1] << endl;
  270.             //cerr << "remove == " << b[j - D - 2] << endl;
  271.             S.insert(b[++last]);
  272.             //S.erase(S.end());
  273.             //cerr << "rem == " << j - D - 2 << endl;
  274.             S.erase(S.find(b[ins++]));
  275.             //cerr << "removed" << endl;
  276.             int cur = getSum(ii, j - B + 1, ii + A - 1, j) - *S.begin();
  277.             if(cur >= ans)
  278.             {
  279.                 ans = cur;
  280.                 res = mp(ii, j - B + 1);
  281.             }
  282.         }
  283.     }
  284.  
  285.     //cerr << "RES == " << res.x << ' ' << res.y << endl;
  286.     assert(ans >= 0);
  287.     return ans;
  288. }
  289.  
  290. inline void solve()
  291. {
  292.     //buildMin();
  293.  
  294.     forn1(i, n)
  295.     {
  296.         int s = 0;
  297.         forn1(j, m)
  298.         {
  299.             s += a[i][j];
  300.             sum[i][j] = sum[i - 1][j] + s;
  301.         }
  302.     }
  303.  
  304.     forn1(i, n)
  305.     {
  306.         forn1(j, m)
  307.         {
  308.             if(i + C - 1 > n || j + D - 1 > m)
  309.                 continue;
  310.             aa[i][j] = getSum(i, j, i + C - 1, j + D - 1);
  311.         }
  312.     }
  313.  
  314.     buildMin();
  315.  
  316.     pt res1 = mp(0, 0);
  317.     int ans = solve(res1);
  318. #ifdef _DEBUG
  319.     int nans = naive();
  320.     if(ans != nans)
  321.     {
  322.         cerr << ans << ' ' << nans << endl;
  323.         assert(false);
  324.     }
  325. #endif
  326.  
  327.     pt res2 = mp(0, 0);
  328.     int mn = INF;
  329.  
  330.     for(int i = res1.x + 1; i <= res1.x + A - 1; i++)
  331.     {
  332.         for(int j = res1.y + 1; j <= res1.y + B - 1; j++)
  333.         {
  334.             if(i + C - 1 >= res1.x + A - 1 || j + D - 1 >= res1.y + B - 1)
  335.                 continue;
  336.             int cur = getSum(i, j, i + C - 1, j + D - 1);
  337.             if(cur < mn)
  338.             {
  339.                 mn = cur;
  340.                 res2 = mp(i, j);
  341.             }
  342.         }
  343.     }
  344.     cerr << ans << endl;
  345.     swap(res1.x, res1.y);
  346.     swap(res2.x, res2.y);
  347.     cout << res1.x << ' ' << res1.y << endl;
  348.     cout << res2.x << ' ' << res2.y << endl;
  349.     return;
  350. }
  351.  
  352. int main() {
  353. #ifdef _DEBUG
  354.     assert(freopen("input.txt", "rt", stdin));
  355.     assert(freopen("output.txt", "wt", stdout));
  356. #endif
  357.  
  358.     cout << setprecision(10) << fixed;
  359.     cerr << setprecision(10) << fixed;
  360.  
  361.     srand(int(time(NULL)));
  362.  
  363.     forn(i, 1)
  364.     {
  365.         assert(read());
  366.         solve();
  367.     }
  368.  
  369. #ifdef _DEBUG
  370.     cerr << "TIME == " << clock() << " ms" << endl;
  371. #endif
  372.     return 0;
  373. }
Advertisement
Add Comment
Please, Sign In to add comment