Submission #338055

#	Time	Username	Problem	Language	Result	Execution time	Memory
338055		boykut	UFO (IZhO14_ufo)	C++14	5 / 100	2107 ms	203812 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> 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 / 100