Submission #338048

#	Time	Username	Problem	Language	Result	Execution time	Memory
338048		boykut	UFO (IZhO14_ufo)	C++14	30 / 100	2090 ms	19880 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   int n, m, k, r, p;
   cin >> n >> m >> r >> k >> p;
   
   vector < vector <int> > a(1+n, vector <int> (1+m,0));
   vector < vector <int> > sum(1+n, vector <int> (1+m,0));
   
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         cin >> a[i][j];
      }
   }
   
   for (int tmp = k; tmp--;) {
      char c; cin >> c;
      int pos, h; cin >> pos >> h;
      if (c == 'N') {
         int cnt = 0;
         for (int i = 1; i <= n; i++) {
            if (a[i][pos] >= h) {
               a[i][pos]--;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else if (c == 'S') {
         int cnt = 0;
         for (int i = n; i >= 1; i--) {
            if (a[i][pos] >= h) {
               a[i][pos]--;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else if (c == 'W') {
         int cnt = 0;
         for (int j = 1; j <= m; j++) {
            if (a[pos][j] >= h) {
               a[pos][j]--;
               cnt++;
               if (cnt == r) break;
            }
         }
      } else {
         int cnt = 0;
         for (int j = m; j >= 1; j--) {
            if (a[pos][j] >= h) {
               a[pos][j]--;
               cnt++;
               if (cnt == r) break;
            }
         }
      }
   }
   
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         sum[i][j] = a[i][j];
         sum[i][j] += sum[i-1][j];
         sum[i][j] += sum[i][j-1];
         sum[i][j] -= sum[i-1][j-1];
      }
   }
   
   int ans = 0, A, i2, j2;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         i2 = i + p - 1, j2 = j + p - 1;
         if (i2 <= n && j2 <= m) {
            A = sum[i2][j2];
            A -= sum[i2][j-1];
            A -= sum[i-1][j2];
            A += sum[i-1][j-1];
            if (A > ans)
               ans = A;
         }
      }
   }
   
   cout << ans << '\n';
   
   return 0;
}

• Subtask 1: 30 / 100