Submission #338073

#	Time	Username	Problem	Language	Result	Execution time	Memory
338073		boykut	UFO (IZhO14_ufo)	C++14	60 / 100	2104 ms	172504 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

#define int long long

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--;) {
            if(a[*it][pos]>=h){
               a[*it][pos]--;
               if (a[*it][pos] == 0) del.insert(*it);
               cnt++;if(cnt==r)break;
            }
            it++;
         }
         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--;) {
            if(a[*it][pos]>=h){
               a[*it][pos]--;
               if (a[*it][pos] == 0) del.insert(*it);
               cnt++;if(cnt==r)break;
            }
            it--;
         }
         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--;) {
            if(a[pos][*it]>=h){
               a[pos][*it]--;
               if (a[pos][*it] == 0) del.insert(*it);
               cnt++;if(cnt==r)break;
            }
            it++;
         }
         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--;) {
            if(a[pos][*it]>=h){
               a[pos][*it]--;
               if (a[pos][*it] == 0) del.insert(*it);
               cnt++;if(cnt==r)break;
            }
            it--;
         }
         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 / 100