Submission #523395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523395	2022-02-07T15:17:48 Z	boykut	UFO (IZhO14_ufo)	C++14	0 / 100	2000 ms	9716 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') {
			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;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Incorrect	1 ms	380 KB	Output isn't correct
4	Incorrect	7 ms	576 KB	Output isn't correct
5	Incorrect	661 ms	1904 KB	Output isn't correct
6	Incorrect	170 ms	9716 KB	Output isn't correct
7	Execution timed out	2028 ms	5068 KB	Time limit exceeded
8	Execution timed out	2075 ms	4596 KB	Time limit exceeded
9	Execution timed out	2090 ms	4984 KB	Time limit exceeded
10	Execution timed out	2087 ms	4644 KB	Time limit exceeded
11	Execution timed out	2050 ms	4772 KB	Time limit exceeded
12	Execution timed out	2055 ms	5012 KB	Time limit exceeded
13	Execution timed out	2056 ms	8176 KB	Time limit exceeded
14	Execution timed out	2059 ms	4588 KB	Time limit exceeded
15	Execution timed out	2027 ms	4880 KB	Time limit exceeded
16	Execution timed out	2060 ms	4676 KB	Time limit exceeded
17	Execution timed out	2071 ms	8244 KB	Time limit exceeded
18	Execution timed out	2062 ms	9620 KB	Time limit exceeded
19	Execution timed out	2066 ms	5036 KB	Time limit exceeded
20	Execution timed out	2048 ms	8140 KB	Time limit exceeded