답안 #338073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338073	2020-12-22T12:20:37 Z	boykut	UFO (IZhO14_ufo)	C++14	60 / 100	2000 ms	172504 KB

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.0 / 100.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	455 ms	54380 KB	Output is correct
7	Execution timed out	2092 ms	116316 KB	Time limit exceeded
8	Execution timed out	2089 ms	116188 KB	Time limit exceeded
9	Correct	989 ms	113272 KB	Output is correct
10	Correct	817 ms	116316 KB	Output is correct
11	Correct	663 ms	113216 KB	Output is correct
12	Correct	747 ms	116444 KB	Output is correct
13	Correct	865 ms	122604 KB	Output is correct
14	Correct	533 ms	113088 KB	Output is correct
15	Execution timed out	2086 ms	116188 KB	Time limit exceeded
16	Execution timed out	2048 ms	113344 KB	Time limit exceeded
17	Execution timed out	2094 ms	122604 KB	Time limit exceeded
18	Execution timed out	2104 ms	109292 KB	Time limit exceeded
19	Execution timed out	2081 ms	122448 KB	Time limit exceeded
20	Execution timed out	2101 ms	172504 KB	Time limit exceeded