Submission #523388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523388	2022-02-07T15:10:31 Z	boykut	UFO (IZhO14_ufo)	C++14	35 / 100	2000 ms	15760 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') {
			for (int j = 0; j < m && cnt > 0; j++) {
				if (a[x][j] >= y) {
					a[x][j]--;
					cnt--;
				}
			}
		} 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

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	4 ms	460 KB	Output is correct
5	Correct	14 ms	1588 KB	Output is correct
6	Correct	57 ms	9272 KB	Output is correct
7	Execution timed out	2008 ms	10376 KB	Time limit exceeded
8	Execution timed out	2093 ms	6916 KB	Time limit exceeded
9	Execution timed out	2055 ms	7036 KB	Time limit exceeded
10	Execution timed out	2064 ms	7292 KB	Time limit exceeded
11	Execution timed out	2086 ms	6524 KB	Time limit exceeded
12	Execution timed out	2041 ms	7356 KB	Time limit exceeded
13	Execution timed out	2020 ms	10672 KB	Time limit exceeded
14	Correct	1915 ms	15760 KB	Output is correct
15	Execution timed out	2031 ms	7936 KB	Time limit exceeded
16	Execution timed out	2036 ms	6384 KB	Time limit exceeded
17	Execution timed out	2025 ms	13624 KB	Time limit exceeded
18	Execution timed out	2036 ms	10800 KB	Time limit exceeded
19	Execution timed out	2077 ms	6656 KB	Time limit exceeded
20	Execution timed out	2025 ms	8124 KB	Time limit exceeded