Submission #523401

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523401	2022-02-07T15:22:11 Z	boykut	UFO (IZhO14_ufo)	C++14	30 / 100	2000 ms	9724 KB

ufo

#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') {
			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 = m - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) / 2;
					if (getmax(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') {
			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;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	248 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	9 ms	480 KB	Output is correct
5	Correct	1436 ms	1404 KB	Output is correct
6	Correct	235 ms	7100 KB	Output is correct
7	Execution timed out	2020 ms	4804 KB	Time limit exceeded
8	Execution timed out	2072 ms	5108 KB	Time limit exceeded
9	Execution timed out	2033 ms	4804 KB	Time limit exceeded
10	Execution timed out	2071 ms	4916 KB	Time limit exceeded
11	Execution timed out	2067 ms	4864 KB	Time limit exceeded
12	Execution timed out	2057 ms	4668 KB	Time limit exceeded
13	Execution timed out	2047 ms	8468 KB	Time limit exceeded
14	Execution timed out	2069 ms	4680 KB	Time limit exceeded
15	Execution timed out	2101 ms	4792 KB	Time limit exceeded
16	Execution timed out	2050 ms	5080 KB	Time limit exceeded
17	Execution timed out	2097 ms	8344 KB	Time limit exceeded
18	Execution timed out	2078 ms	9724 KB	Time limit exceeded
19	Execution timed out	2055 ms	4916 KB	Time limit exceeded
20	Execution timed out	2066 ms	8140 KB	Time limit exceeded