Submission #338024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338024	2020-12-22T09:22:37 Z	boykut	UFO (IZhO14_ufo)	C++14	25 / 100	2000 ms	9964 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	748 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Incorrect	15 ms	492 KB	Output isn't correct
6	Correct	66 ms	6380 KB	Output is correct
7	Execution timed out	2088 ms	748 KB	Time limit exceeded
8	Execution timed out	2090 ms	748 KB	Time limit exceeded
9	Execution timed out	2081 ms	620 KB	Time limit exceeded
10	Execution timed out	2093 ms	748 KB	Time limit exceeded
11	Execution timed out	2055 ms	1004 KB	Time limit exceeded
12	Execution timed out	2077 ms	748 KB	Time limit exceeded
13	Runtime error	21 ms	9836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Incorrect	1313 ms	1292 KB	Output isn't correct
15	Execution timed out	2048 ms	748 KB	Time limit exceeded
16	Execution timed out	2079 ms	876 KB	Time limit exceeded
17	Runtime error	21 ms	9836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	11 ms	9964 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Execution timed out	2071 ms	1132 KB	Time limit exceeded
20	Execution timed out	2087 ms	4204 KB	Time limit exceeded