Submission #338170

#	Time	Username	Problem	Language	Result	Execution time	Memory
338170		boykut	UFO (IZhO14_ufo)	C++14	85 / 100	994 ms	172632 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;
   
   if (n * m <= 500000) {
      int a[n][m];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            cin >> a[i][j];
         }
      }
      
      for (int i = 0; i < k; i++) {
         char ch; cin >> ch;
         int pos, h; cin >> pos >> h;
         pos--;
         if (ch == 'N') {
            int cnt = 0;
            for (int i = 0; i < n && cnt < r; i++) {
               if (a[i][pos] >= h) {
                  a[i][pos] --;
                  cnt++;
                  if (cnt == r) break;
               }
            }
         } else if (ch == 'E') {
            int cnt = 0;
            for (int i = m - 1; i >= 0 && cnt < r; i--) {
               if (a[pos][i] >= h) {
                  a[pos][i] --;
                  cnt++;
                  if (cnt == r) break;
               }
            }
         } else if (ch == 'W') {
            int cnt = 0;
            for (int i = 0; i < m && cnt < r; i++) {
               if (a[pos][i] >= h) {
                  a[pos][i] --;
                  cnt++;
                  if (cnt == r) break;
               }
            }
         } else {
            int cnt = 0;
            for (int i = n - 1; i >= 0 && cnt < r; i--) {
               if (a[i][pos] >= h) {
                  a[i][pos] --;
                  cnt++;
                  if (cnt == r) break;
               }
            }
         }
      }
      
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
           //cout << a[i][j] << ' ';
         }
         //cout << '\n';
      }
      
      int sum = 0, ans = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (i + p <= n && j + p <= m) {
               sum = 0;
               for (int i1 = i; i1 < i + p; i1++) {
                  for (int j1 = j; j1 < j + p; j1++) {
                     sum += a[i1][j1];
                  }
               }
               if (sum > ans) {
                  //cout << i << ' ' << j << '\n';
                  ans = sum;
                  //cout << sum << "\n\n";
               }
            }
         }
      }
      
      cout << ans << '\n';
   } else {
      
      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: 85 / 100