Submission #338024

#	Time	Username	Problem	Language	Result	Execution time	Memory
338024		boykut	UFO (IZhO14_ufo)	C++14	25 / 100	2093 ms	9964 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

int a[1111][1111];
int sp[1111][1111];


int get(int i1, int j1, int i2, int j2) {
   int A = sp[i2][j2];
   int B = (i1?sp[i1-1][j2]:0);
   int C = (j1?sp[i2][j1-1]:0);
   int D = (i1&&j1?sp[i1-1][j1-1]:0);
   return A-B-C+D;
};

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   int n, m, k, r, p;
   cin >> n >> m >> r >> k >> p;
   
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         cin >> a[i][j];
      }
   }
   
   for (int i = 0; i < k; i++) {
      char ch; cin >> ch;
      int pos, h; cin >> pos >> h;
      pos--;
      if (ch == 'N') {
         int cnt = 0;
         for (int i = 0; i < n && cnt < r; i++) {
            if (a[i][pos] >= h) {
               a[i][pos] --;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else if (ch == 'E') {
         int cnt = 0;
         for (int i = m - 1; i >= 0 && cnt < r; i--) {
            if (a[pos][i] >= h) {
               a[pos][i] --;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else if (ch == 'W') {
         int cnt = 0;
         for (int i = 0; i < m && cnt < r; i++) {
            if (a[pos][i] >= h) {
               a[pos][i] --;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else {
         int cnt = 0;
         for (int i = n - 1; i >= 0 && cnt < r; i--) {
            if (a[i][pos] >= h) {
               a[i][pos] --;
               cnt++;
               if (cnt == r) break;
            }
         }
      }
   }
   
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        //cout << a[i][j] << ' ';
      }
      //cout << '\n';
   }
   
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         int A = (i?sp[i-1][j]:0);
         int B = (j?sp[i][j-1]:0);
         int C = (i&&j?sp[i-1][j-1]:0);
         sp[i][j]=a[i][j]+A+B-C;
      }
   }
   
   int sum = 0, ans = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         if (i + p - 1 < n && j + p - 1 < m) {
            sum = get(i, j, i+p-1, j+p-1);
            if (sum > ans) {
               //cout << i << ' ' << j << '\n';
               ans = sum;
               //cout << sum << "\n\n";
            }
         }
      }
   }
   
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 25 / 100