Submission #338070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338070	2020-12-22T12:13:29 Z	boykut	UFO (IZhO14_ufo)	C++14	60 / 100	895 ms	159780 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;
   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);
         }
      }
   }
   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 (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 (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 (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 (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);
         }
      }
      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:19:14: warning: unused variable 'cnt' [-Wunused-variable]
   19 |    int temp, cnt;
      |              ^~~

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	2 ms	620 KB	Output isn't correct
4	Incorrect	7 ms	1388 KB	Output isn't correct
5	Incorrect	50 ms	5740 KB	Output isn't correct
6	Incorrect	287 ms	50540 KB	Output isn't correct
7	Correct	666 ms	107620 KB	Output is correct
8	Correct	895 ms	107620 KB	Output is correct
9	Correct	870 ms	105000 KB	Output is correct
10	Correct	890 ms	107556 KB	Output is correct
11	Correct	642 ms	104724 KB	Output is correct
12	Correct	842 ms	107620 KB	Output is correct
13	Correct	888 ms	116264 KB	Output is correct
14	Correct	541 ms	104596 KB	Output is correct
15	Incorrect	662 ms	107748 KB	Output isn't correct
16	Correct	755 ms	104596 KB	Output is correct
17	Incorrect	669 ms	116276 KB	Output isn't correct
18	Correct	758 ms	101752 KB	Output is correct
19	Incorrect	812 ms	113244 KB	Output isn't correct
20	Correct	790 ms	159780 KB	Output is correct