Submission #39052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
39052	2018-01-09T06:32:04 Z	RockyB	UFO (IZhO14_ufo)	C++14	75 / 100	2000 ms	10568 KB

ufo

/// In The Name Of God
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
 
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define nl '\n'
#define ioi exit(0);
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)5e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
using namespace std;

int get_int() {
	char x = getchar();
	while (!isdigit(x)) x = getchar();
	int res = 0;
	while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
	return res;
}
char get_char() {
	char x = getchar();
	while (!isalpha(x)) x = getchar();
	return x;
}
 
int n, m, r, k, p;
vector < vector <int> > a;
int get(int x1, int y1) {
	int res = 0;
	int x2 = x1 + p - 1, y2 = y1 + p - 1;
	return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
	for (int i = x1; i <= x2; i++) {
		for (int j = y1; j <= y2; j++) {
			res += a[i][j];
		}
	}
	return res;
}
void build() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] += a[i - 1][j];
			a[i][j] += a[i][j - 1];
			a[i][j] -= a[i - 1][j - 1];
		}
	}
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	n = get_int(), m = get_int(), r = get_int(), k = get_int(), p = get_int();
	a.resize(n + 2);
	a[0].resize(m + 2);
	for (int i = 1; i <= n; i++) {
		a[i].resize(m + 2);
		for (int j = 1; j <= m; j++) {
			a[i][j] = get_int();
		}
	}
	for (int t = 1; t <= k; t++) {
		char c = get_char();
		int x = get_int(), y = get_int();
		if (c == 'S') {
			for (int i = n, done = 0, total = 0; done < r && i >= 1 && total <= 2500; i--, total++) {
				if (a[i][x] >= y) a[i][x]--, done++;
			}
		}
		else if (c == 'N') {
			for (int i = 1, done = 0, total = 0; done < r && i <= n && total <= 2500; i++, total++) {
				if (a[i][x] >= y) a[i][x]--, done++;
			}
		}
		else if (c == 'W') {
			for (int i = 1, done = 0, total = 0; done < r && i <= m && total <= 2500; i++, total++) {
				if (a[x][i] >= y) a[x][i]--, done++;
			}
		}
		else {
			for (int i = m, done = 0, total = 0; done < r && i >= 1 && total <= 2500; i--, total++) {
				if (a[x][i] >= y) a[x][i]--, done++;
			}
		}
	}
	int ans = 0;
	build();
	for (int i = 1; i <= n - p + 1; i++) {
		for (int j = 1; j <= m - p + 1; j++) {
			ans = max(ans, get(i, j));
		}
	}
	cout << ans;
	ioi
}

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2020 KB	Output is correct
2	Correct	0 ms	2020 KB	Output is correct
3	Correct	0 ms	2020 KB	Output is correct
4	Correct	3 ms	2020 KB	Output is correct
5	Correct	6 ms	2292 KB	Output is correct
6	Correct	53 ms	4000 KB	Output is correct
7	Correct	769 ms	6332 KB	Output is correct
8	Correct	733 ms	6332 KB	Output is correct
9	Incorrect	616 ms	6136 KB	Output isn't correct
10	Correct	599 ms	6332 KB	Output is correct
11	Incorrect	599 ms	6268 KB	Output isn't correct
12	Correct	616 ms	6332 KB	Output is correct
13	Correct	1986 ms	10568 KB	Output is correct
14	Correct	623 ms	6268 KB	Output is correct
15	Incorrect	686 ms	6332 KB	Output isn't correct
16	Correct	1113 ms	6268 KB	Output is correct
17	Execution timed out	2000 ms	10568 KB	Execution timed out
18	Correct	1799 ms	10512 KB	Output is correct
19	Incorrect	999 ms	6724 KB	Output isn't correct
20	Correct	1049 ms	9836 KB	Output is correct