답안 #338076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338076 2020-12-22T12:25:17 Z boykut UFO (IZhO14_ufo) C++14
60 / 100
2000 ms 172576 KB
#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 <= 1000) {
      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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 10 ms 1388 KB Output is correct
5 Correct 46 ms 6124 KB Output is correct
6 Correct 450 ms 54124 KB Output is correct
7 Execution timed out 2078 ms 116444 KB Time limit exceeded
8 Execution timed out 2083 ms 116188 KB Time limit exceeded
9 Correct 987 ms 113252 KB Output is correct
10 Correct 842 ms 116188 KB Output is correct
11 Correct 660 ms 113132 KB Output is correct
12 Correct 832 ms 116316 KB Output is correct
13 Correct 881 ms 122604 KB Output is correct
14 Correct 582 ms 113256 KB Output is correct
15 Execution timed out 2028 ms 116444 KB Time limit exceeded
16 Execution timed out 2103 ms 113088 KB Time limit exceeded
17 Execution timed out 2090 ms 122732 KB Time limit exceeded
18 Execution timed out 2102 ms 109548 KB Time limit exceeded
19 Execution timed out 2104 ms 122480 KB Time limit exceeded
20 Execution timed out 2108 ms 172576 KB Time limit exceeded