답안 #523388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523388 2022-02-07T15:10:31 Z boykut UFO (IZhO14_ufo) C++14
35 / 100
2000 ms 15760 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>,
rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<vector<int>> a;
vector<vector<long long>> pref;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;

	a = vector<vector<int>>(n, vector<int>(m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	while (k--) {
		char c; cin >> c;
		int x, y; cin >> x >> y;
		int cnt = r;
		x--;
		if (c == 'W') {
			for (int j = 0; j < m && cnt > 0; j++) {
				if (a[x][j] >= y) {
					a[x][j]--;
					cnt--;
				}
			}
		} else if (c == 'E') {
			for (int j = m - 1; j >= 0 && cnt > 0; j--) {
				if (a[x][j] >= y) {
					a[x][j]--;
					cnt--;
				}
			}
		} else if (c == 'N') {
			for (int i = 0; i < n && cnt > 0; i++) {
				if (a[i][x] >= y) {
					a[i][x]--;
					cnt--;
				}
			}
		} else {
			for (int i = n - 1; i >= 0 && cnt > 0; i--) {
				if (a[i][x] >= y) {
					a[i][x]--;
					cnt--;
				}
			}
		}
	}

	pref = vector<vector<long long>>(n, vector<long long>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//cout << a[i][j] << ' ';
			pref[i][j] = a[i][j];
			pref[i][j] += (i ? pref[i-1][j] : 0);
			pref[i][j] += (j ? pref[i][j-1] : 0);
			pref[i][j] -= (i && j ? pref[i-1][j-1] : 0);
		}
		//cout << '\n';
	}

	auto get = [&](int a, int b, int c, int d) ->long long {
		long long s = pref[c][d];
		s -= (a ? pref[a-1][d] : 0);
		s -= (b ? pref[c][b-1] : 0);
		s += (a && b ? pref[a-1][b-1] : 0);
		return s;
	};

	long long ans = LLONG_MIN;
	for (int i = 0; i + p - 1 < n; i++) {
		for (int j = 0; j + p - 1 < m; j++) {
			ans = max(ans, get(i, j, i + p - 1, j + p - 1));
		}
	}
	cout << ans << '\n';

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 14 ms 1588 KB Output is correct
6 Correct 57 ms 9272 KB Output is correct
7 Execution timed out 2008 ms 10376 KB Time limit exceeded
8 Execution timed out 2093 ms 6916 KB Time limit exceeded
9 Execution timed out 2055 ms 7036 KB Time limit exceeded
10 Execution timed out 2064 ms 7292 KB Time limit exceeded
11 Execution timed out 2086 ms 6524 KB Time limit exceeded
12 Execution timed out 2041 ms 7356 KB Time limit exceeded
13 Execution timed out 2020 ms 10672 KB Time limit exceeded
14 Correct 1915 ms 15760 KB Output is correct
15 Execution timed out 2031 ms 7936 KB Time limit exceeded
16 Execution timed out 2036 ms 6384 KB Time limit exceeded
17 Execution timed out 2025 ms 13624 KB Time limit exceeded
18 Execution timed out 2036 ms 10800 KB Time limit exceeded
19 Execution timed out 2077 ms 6656 KB Time limit exceeded
20 Execution timed out 2025 ms 8124 KB Time limit exceeded