Submission #338062

#	Time	Username	Problem	Language	Result	Execution time	Memory
338062		boykut	UFO (IZhO14_ufo)	C++14	55 / 100	1840 ms	262148 KiB

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> col2[1+m];
   set <int> row2[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);
            row2[i].insert(-j);
            col2[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;
         int cnt = 0;
         for (auto i: col[pos]) {
            a[i][pos]--;
            if (a[i][pos] == 0) del.insert(i), row[i].erase(pos), row2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'S') {
         if (col2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: col2[pos]) {
            a[-i][pos]--;
            if (a[-i][pos] == 0) del.insert(-i), row[-i].erase(pos), row2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'W') {
         if (row[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row[pos]) {
            a[pos][i]--;
            if (a[pos][i] == 0) del.insert(i), col[i].erase(pos), col2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      } else {
         if (row2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row2[pos]) {
            a[pos][-i]--;
            if (a[pos][-i] == 0) del.insert(-i), col[-i].erase(pos), col2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      }
      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 (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:21:8: warning: unused variable 'temp' [-Wunused-variable]
   21 |    int temp, cnt;
      |        ^~~~
ufo.cpp:21:14: warning: unused variable 'cnt' [-Wunused-variable]
   21 |    int temp, cnt;
      |              ^~~

• Subtask 1: 55 / 100