Submission #338062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338062	2020-12-22T11:55:56 Z	boykut	UFO (IZhO14_ufo)	C++14	55 / 100	1840 ms	262148 KB

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));
   
   set <int> col[1+m];
   set <int> row[1+n];
   set <int> col2[1+m];
   set <int> row2[1+n];
   set <int> del;
   set <int>::iterator it;
   int temp, cnt;
   
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         cin >> a[i][j];
         if (a[i][j] != 0) {
            row[i].insert(j);
            col[j].insert(i);
            row2[i].insert(-j);
            col2[j].insert(-i);
         }
      }
   }
   for (int tmp = k; tmp--;) {
      char c; cin >> c;
      int pos, h; cin >> pos >> h;
      if (c == 'N') {
         if (col[pos].empty()) continue;
         int cnt = 0;
         for (auto i: col[pos]) {
            a[i][pos]--;
            if (a[i][pos] == 0) del.insert(i), row[i].erase(pos), row2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'S') {
         if (col2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: col2[pos]) {
            a[-i][pos]--;
            if (a[-i][pos] == 0) del.insert(-i), row[-i].erase(pos), row2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'W') {
         if (row[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row[pos]) {
            a[pos][i]--;
            if (a[pos][i] == 0) del.insert(i), col[i].erase(pos), col2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      } else {
         if (row2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row2[pos]) {
            a[pos][-i]--;
            if (a[pos][-i] == 0) del.insert(-i), col[-i].erase(pos), col2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      }
      del.clear();
   }
   
   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;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:21:8: warning: unused variable 'temp' [-Wunused-variable]
   21 |    int temp, cnt;
      |        ^~~~
ufo.cpp:21:14: warning: unused variable 'cnt' [-Wunused-variable]
   21 |    int temp, cnt;
      |              ^~~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	364 KB	Output isn't correct
3	Incorrect	2 ms	896 KB	Output isn't correct
4	Incorrect	11 ms	2304 KB	Output isn't correct
5	Incorrect	72 ms	10604 KB	Output isn't correct
6	Incorrect	668 ms	96620 KB	Output isn't correct
7	Correct	1279 ms	206220 KB	Output is correct
8	Correct	1624 ms	206436 KB	Output is correct
9	Correct	1840 ms	201640 KB	Output is correct
10	Correct	1619 ms	206820 KB	Output is correct
11	Correct	1226 ms	201108 KB	Output is correct
12	Correct	1495 ms	206820 KB	Output is correct
13	Correct	1551 ms	215916 KB	Output is correct
14	Correct	1095 ms	200724 KB	Output is correct
15	Incorrect	1245 ms	207588 KB	Output isn't correct
16	Correct	1379 ms	200596 KB	Output is correct
17	Incorrect	1235 ms	217180 KB	Output isn't correct
18	Correct	1370 ms	186884 KB	Output is correct
19	Incorrect	1424 ms	218968 KB	Output isn't correct
20	Runtime error	630 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)