Submission #338071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338071	2020-12-22T12:15:02 Z	boykut	UFO (IZhO14_ufo)	C++14	60 / 100	896 ms	156964 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> del;
   set <int>::iterator it;
   
   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);
         }
      }
   }
   for (int tmp = k; tmp--;) {
      char c; cin >> c;
      int pos, h; cin >> pos >> h;
      if (c == 'N') {
         if (col[pos].empty()) continue;
         it = col[pos].begin();
         int cnt = 0;
         for (int temp = col[pos].size(); temp--;) {
            a[*it][pos]--;
            if (a[*it][pos] == 0) del.insert(*it);
            it++;
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            row[i].erase(pos);
         }
      } else if (c == 'S') {
         if (col[pos].empty()) continue;
         it = col[pos].end(); it--;
         int cnt = 0;
         for (int temp = col[pos].size(); temp--;) {
            a[*it][pos]--;
            if (a[*it][pos] == 0) del.insert(*it);
            it--;
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            row[i].erase(pos);
         }
      } else if (c == 'W') {
         if (row[pos].empty()) continue;
         it = row[pos].begin();
         int cnt = 0;
         for (int temp = row[pos].size(); temp--;) {
            a[pos][*it]--;
            if (a[pos][*it] == 0) del.insert(*it);
            it++;
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            col[i].erase(pos);
         }
      } else {
         if (row[pos].empty()) continue;
         it = row[pos].end(); it--;
         int cnt = 0;
         for (int temp = row[pos].size(); temp--;) {
            a[pos][*it]--;
            if (a[pos][*it] == 0) del.insert(*it);
            it--;
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            col[i].erase(pos);
         }
      }
      while (!del.empty())
         del.erase(del.begin());
   }
   
   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

60.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	1 ms	620 KB	Output isn't correct
4	Incorrect	9 ms	1388 KB	Output isn't correct
5	Incorrect	47 ms	5872 KB	Output isn't correct
6	Incorrect	290 ms	50356 KB	Output isn't correct
7	Correct	673 ms	107620 KB	Output is correct
8	Correct	890 ms	107748 KB	Output is correct
9	Correct	896 ms	104904 KB	Output is correct
10	Correct	890 ms	107748 KB	Output is correct
11	Correct	702 ms	104724 KB	Output is correct
12	Correct	849 ms	107764 KB	Output is correct
13	Correct	864 ms	116308 KB	Output is correct
14	Correct	540 ms	104596 KB	Output is correct
15	Incorrect	662 ms	107764 KB	Output isn't correct
16	Correct	782 ms	104724 KB	Output is correct
17	Incorrect	653 ms	116332 KB	Output isn't correct
18	Correct	753 ms	101996 KB	Output is correct
19	Incorrect	793 ms	113088 KB	Output isn't correct
20	Correct	815 ms	156964 KB	Output is correct