답안 #523411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523411 2022-02-07T15:32:28 Z boykut UFO (IZhO14_ufo) C++14
30 / 100
2000 ms 8780 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 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;
};

int 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;
};

void updateRow(int x, int j) {
	a[x][j]--;
}
void updateCol(int x, int j) {
	a[j][x]--;
}

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') {
			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) {
					updateRow(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) {
					updateRow(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) {
					updateCol(x, r);
					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) {
					updateCol(x, l);
					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 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 1310 ms 892 KB Output is correct
6 Correct 363 ms 6080 KB Output is correct
7 Execution timed out 2074 ms 4556 KB Time limit exceeded
8 Execution timed out 2064 ms 4556 KB Time limit exceeded
9 Execution timed out 2069 ms 4428 KB Time limit exceeded
10 Execution timed out 2062 ms 4556 KB Time limit exceeded
11 Execution timed out 2082 ms 4556 KB Time limit exceeded
12 Execution timed out 2070 ms 4556 KB Time limit exceeded
13 Execution timed out 2069 ms 7244 KB Time limit exceeded
14 Execution timed out 2066 ms 4556 KB Time limit exceeded
15 Execution timed out 2084 ms 4556 KB Time limit exceeded
16 Execution timed out 2080 ms 4556 KB Time limit exceeded
17 Execution timed out 2078 ms 7244 KB Time limit exceeded
18 Execution timed out 2093 ms 8780 KB Time limit exceeded
19 Execution timed out 2087 ms 4940 KB Time limit exceeded
20 Execution timed out 2071 ms 8140 KB Time limit exceeded