Submission #338055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338055	2020-12-22T11:36:07 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];
         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;
         cnt = 0;
         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;
         cnt = 0;
         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;
         cnt = 0;
         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;
         cnt = 0;
         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	0 ms	364 KB	Output isn't correct
3	Incorrect	2 ms	620 KB	Output isn't correct
4	Incorrect	31 ms	1388 KB	Output isn't correct
5	Execution timed out	2095 ms	5868 KB	Time limit exceeded
6	Execution timed out	2098 ms	50412 KB	Time limit exceeded
7	Execution timed out	2103 ms	112292 KB	Time limit exceeded
8	Execution timed out	2101 ms	112228 KB	Time limit exceeded
9	Execution timed out	2098 ms	107360 KB	Time limit exceeded
10	Execution timed out	2068 ms	112228 KB	Time limit exceeded
11	Execution timed out	2077 ms	110228 KB	Time limit exceeded
12	Execution timed out	2107 ms	112228 KB	Time limit exceeded
13	Execution timed out	2105 ms	120812 KB	Time limit exceeded
14	Execution timed out	2105 ms	110228 KB	Time limit exceeded
15	Execution timed out	2065 ms	112348 KB	Time limit exceeded
16	Execution timed out	2104 ms	110228 KB	Time limit exceeded
17	Execution timed out	2106 ms	120812 KB	Time limit exceeded
18	Execution timed out	2101 ms	107560 KB	Time limit exceeded
19	Execution timed out	2089 ms	122460 KB	Time limit exceeded
20	Execution timed out	2073 ms	203812 KB	Time limit exceeded