답안 #523406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523406 2022-02-07T15:27:42 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--;

		auto getmaxRow = [&](int x, int l, int r) {
			int ans = INT_MIN;
			for (int j = l; j <= r; j++) ans = max(ans, a[x][j]);
			return ans;
		};
		auto getmaxCol = [&](int x, int l, int r) {
			int ans = INT_MIN;
			for (int j = l; j <= r; j++) ans = max(ans, a[j][x]);
			return ans;
		};

		if (c == 'W') {
			int start = 0;
			while (cnt > 0 && start < m) {
				int l = start, r = m - 1;
				while (l < r) {
					int m = (l + r) / 2;
					if (getmaxRow(x, 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') {
			int start = m - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) / 2;
					if (getmaxRow(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (a[x][l] >= y) {
					a[x][l]--;
					cnt--;
					start = l - 1;
				} else break;
			}
		} else if (c == 'N') {
			int start = 0;
			while (cnt > 0 && start < n) {
				int l = start, r = n - 1;
				while (l < r) {
					int m = (l + r) / 2;
					if (getmaxCol(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (a[r][x] >= y) {
					a[r][x]--;
					cnt--;
					start = r + 1;
				} else break;
			}
		} else {
			int start = n - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) / 2;
					if (getmaxCol(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (a[l][x] >= y) {
					a[l][x]--;
					cnt--;
					start = l - 1;
				} else break;
			}
		}
	}

	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 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 12 ms 356 KB Output is correct
5 Correct 1251 ms 900 KB Output is correct
6 Correct 346 ms 6092 KB Output is correct
7 Execution timed out 2080 ms 4556 KB Time limit exceeded
8 Execution timed out 2044 ms 4556 KB Time limit exceeded
9 Execution timed out 2093 ms 4428 KB Time limit exceeded
10 Execution timed out 2069 ms 4556 KB Time limit exceeded
11 Execution timed out 2087 ms 4556 KB Time limit exceeded
12 Execution timed out 2086 ms 4556 KB Time limit exceeded
13 Execution timed out 2081 ms 7244 KB Time limit exceeded
14 Execution timed out 2083 ms 4556 KB Time limit exceeded
15 Execution timed out 2085 ms 4556 KB Time limit exceeded
16 Execution timed out 2095 ms 4556 KB Time limit exceeded
17 Execution timed out 2097 ms 7244 KB Time limit exceeded
18 Execution timed out 2086 ms 8652 KB Time limit exceeded
19 Execution timed out 2097 ms 4940 KB Time limit exceeded
20 Execution timed out 2099 ms 8140 KB Time limit exceeded