답안 #523397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523397 2022-02-07T15:19:15 Z boykut UFO (IZhO14_ufo) C++14
30 / 100
2000 ms 8652 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') {
			auto getmax = [&](int l, int r) {
				int ans = INT_MIN;
				for (int j = l; j <= r; j++) ans = max(ans, a[x][j]);
				return ans;
			};
			int start = 0;
			while (cnt > 0 && start < m) {
				int l = start, r = m - 1;
				while (l < r) {
					int m = (l + r) / 2;
					if (getmax(start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (a[x][r] >= y) {
					a[x][r]--;
					cnt--;
					start = r + 1;
				} else break;
			}
		} 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 1 ms 220 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 663 ms 892 KB Output is correct
6 Correct 134 ms 6084 KB Output is correct
7 Execution timed out 2072 ms 4556 KB Time limit exceeded
8 Execution timed out 2074 ms 4556 KB Time limit exceeded
9 Execution timed out 2069 ms 4428 KB Time limit exceeded
10 Execution timed out 2074 ms 4556 KB Time limit exceeded
11 Execution timed out 2072 ms 4556 KB Time limit exceeded
12 Execution timed out 2080 ms 4556 KB Time limit exceeded
13 Execution timed out 2048 ms 7344 KB Time limit exceeded
14 Execution timed out 2076 ms 4556 KB Time limit exceeded
15 Execution timed out 2048 ms 4556 KB Time limit exceeded
16 Execution timed out 2073 ms 4556 KB Time limit exceeded
17 Execution timed out 2070 ms 7244 KB Time limit exceeded
18 Execution timed out 2075 ms 8652 KB Time limit exceeded
19 Execution timed out 2071 ms 4940 KB Time limit exceeded
20 Execution timed out 2084 ms 8140 KB Time limit exceeded