Submission #338059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338059	2020-12-22T11:43:35 Z	boykut	UFO (IZhO14_ufo)	C++14	5 / 100	2000 ms	203812 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> st;
   
   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);
         }
      }
   }
   
   int temp, cnt;
   set <int>::iterator it;
   
   for (int tmp = k; tmp--;) {
      char c; cin >> c;
      int pos, h; cin >> pos >> h;
      if (c == 'N') {
         if (col[pos].empty()) continue;
         st = col[pos];
         it = col[pos].begin();
         for (cnt = 0, temp = col[pos].size(); temp--;) {
            a[*it][pos]--;
            if (a[*it][pos] == 0) st.erase(st.find(*it));
            it++;
            cnt++;
            if (cnt == r) break;
         }
         col[pos] = st;
      } else if (c == 'S') {
         if (col[pos].empty()) continue;
         st = col[pos];
         it = col[pos].end();
         for (cnt = 0, temp = col[pos].size(); temp--;) {
            it--;
            a[*it][pos]--;
            if (a[*it][pos] == 0) st.erase(st.find(*it));
            cnt++;
            if (cnt == r) break;
         }
         col[pos] = st;
      } else if (c == 'W') {
         if (row[pos].empty()) continue;
         st = row[pos];
         it = row[pos].begin();
         for (cnt = 0, temp = row[pos].size(); temp--;) {
            a[pos][*it]--;
            if (a[pos][*it] == 0) st.erase(st.find(*it));
            cnt++;
            it++;
            if (cnt == r) break;
         }
         row[pos] = st;
      } else {
         if (row[pos].empty()) continue;
         st = row[pos];
         it = row[pos].end();
         for (cnt = 0, temp = row[pos].size(); temp--;) {
            it--;
            a[pos][*it]--;
            if (a[pos][*it] == 0) st.erase(st.find(*it));
            cnt++;
            if (cnt == r) break;
         }
         row[pos] = st;
      }
   }
   
   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

5.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	3 ms	620 KB	Output isn't correct
4	Incorrect	30 ms	1388 KB	Output isn't correct
5	Execution timed out	2089 ms	5996 KB	Time limit exceeded
6	Execution timed out	2086 ms	50412 KB	Time limit exceeded
7	Execution timed out	2090 ms	112356 KB	Time limit exceeded
8	Execution timed out	2076 ms	112484 KB	Time limit exceeded
9	Execution timed out	2098 ms	107176 KB	Time limit exceeded
10	Execution timed out	2107 ms	112228 KB	Time limit exceeded
11	Execution timed out	2109 ms	110228 KB	Time limit exceeded
12	Execution timed out	2108 ms	112228 KB	Time limit exceeded
13	Execution timed out	2047 ms	120812 KB	Time limit exceeded
14	Execution timed out	2088 ms	110356 KB	Time limit exceeded
15	Execution timed out	2108 ms	112228 KB	Time limit exceeded
16	Execution timed out	2107 ms	110228 KB	Time limit exceeded
17	Execution timed out	2097 ms	120860 KB	Time limit exceeded
18	Execution timed out	2099 ms	107500 KB	Time limit exceeded
19	Execution timed out	2096 ms	122588 KB	Time limit exceeded
20	Execution timed out	2105 ms	203812 KB	Time limit exceeded