Guest User

Untitled

a guest
Jun 17th, 2015
427
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pii pair<int, int>
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7.  
  8. #define f first
  9. #define s second
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. typedef vector<int> big;
  15.  
  16. const double EPS = 1e-9;
  17. const double PI = acos(-1);
  18.  
  19. const int MAXN = (int) 1e3 + 7;
  20. const int INF = (int) 1e9 + 7;
  21.  
  22. struct minQueue {
  23.   pii sa[MAXN], sb[MAXN];
  24.   int an, bn;
  25.   minQueue() {
  26.     an = bn = 0;
  27.   }
  28.   void push(int x) {
  29.     sb[bn++] = mp(x, bn ? min(sb[bn - 1].s, x) : x);
  30.   }
  31.   void recalc() {
  32.     while (bn) {
  33.       int x = sb[bn - 1].f;
  34.       sa[an++] = mp(x, an ? min(sa[an - 1].s, x) : x);
  35.       bn--;
  36.     }
  37.   }
  38.   int front() {
  39.     assert(an + bn > 0);
  40.     if (!an)
  41.       recalc();
  42.  
  43.     return sa[an - 1].f;
  44.   }
  45.   void pop() {
  46.     assert(an + bn > 0);
  47.     if (!an)
  48.       recalc();
  49.  
  50.     an--;
  51.   }
  52.   int getMin() {
  53.     assert(an + bn > 0);
  54.     if (!an) return sb[bn - 1].s;
  55.     if (!bn) return sa[an - 1].s;
  56.     return min(sa[an - 1].s, sb[bn - 1].s);
  57.   }
  58. };
  59.  
  60. int n, m, a, b, c, d;
  61.  
  62. int f[MAXN][MAXN];
  63. int room[MAXN][MAXN];
  64.  
  65. int pyramid[MAXN][MAXN];
  66.  
  67. int nxtD[MAXN][MAXN];
  68. int nxtB[MAXN][MAXN];
  69.  
  70. int sum[MAXN][MAXN];
  71.  
  72. int main() {
  73.   #ifdef LOCAL
  74.   freopen("in", "r", stdin);
  75.   #else
  76.   //freopen(".in", "r", stdin);
  77.   //freopen(".out", "w", stdout);
  78.   #endif
  79.  
  80.   scanf("%d%d%d%d%d%d", &m, &n, &b, &a, &d, &c);
  81.   for (int i = 1; i <= n; i++) {
  82.     for (int j = 1; j <= m; j++) {
  83.       scanf("%d", &f[i][j]);
  84.       sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + f[i][j];
  85.     }
  86.   }                                          
  87.   for (int i = 1; i <= n - c + 1; i++) {
  88.     for (int j = 1; j <= m - d + 1; j++) {
  89.       int x = i + c - 1;
  90.       int y = j + d - 1;
  91.       room[i][j] = sum[x][y] - sum[x][j - 1] - sum[i - 1][y] + sum[i - 1][j - 1];
  92.     }
  93.   }
  94.   a -= 2;
  95.   b -= 2;
  96.   for (int i = 1; i <= n - c + 1; i++) {
  97.     minQueue cur;
  98.     for (int j = 1; j <= b - d + 1; j++) {
  99.       cur.push(room[i][j]);
  100.     }
  101.     for (int j = 1; j <= (m - d + 1) - (b - d + 1) + 1; j++) {
  102.       nxtB[i][j] = cur.getMin();
  103.       if (j + (b - d + 1) <= m) {
  104.         cur.pop();
  105.         cur.push(room[i][j + b - d + 1]);
  106.       }
  107.     }
  108.   }
  109.   for (int j = 1; j <= (m - d + 1) - (b - d + 1) + 1; j++) {
  110.     minQueue cur;
  111.     for (int i = 1; i <= a - c + 1; i++)
  112.       cur.push(nxtB[i][j]);
  113.     for (int i = 1; i <= n - (a - c + 1) + 1; i++) {
  114.       pyramid[i][j] = cur.getMin();
  115.       if (i + (a - c + 1) <= n) {
  116.         cur.pop();
  117.         cur.push(nxtB[i + a - c + 1][j]);
  118.       }
  119.     }
  120.   }
  121.   a += 2;
  122.   b += 2;
  123.   long long ans = 0;
  124.   int px = 0, py = 0;
  125.   for (int i = 1; i <= n - a + 1; i++) {
  126.     for (int j = 1; j <= m - b + 1; j++) {
  127.       int ex = i + a - 1;
  128.       int ey = j + b - 1;
  129.       long long csum = sum[ex][ey] - sum[i - 1][ey] - sum[ex][j - 1] + sum[i - 1][j - 1];
  130.       csum -= pyramid[i + 1][j + 1];
  131.       if (csum > ans) {
  132.         ans = csum;
  133.         px = i;
  134.         py = j;
  135.       }  
  136.     }
  137.   }
  138.   printf("%d %d\n", py, px);
  139.   //cout<<pyramid[px+1][py+1]<<endl;
  140.   for (int i = px + 1; i + c - 1 < px + a - 1; i++) {
  141.     for (int j = py + 1; j + d - 1 < py + b - 1; j++) {
  142.       if (room[i][j] == pyramid[px + 1][py + 1]) {
  143.         printf("%d %d\n", j, i);
  144.         return 0;
  145.       }  
  146.     }  
  147.   }
  148.   return 0;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment