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
#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;
      |              ^~~
# 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