Submission #39065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
39065	2018-01-09T06:48:20 Z	RockyB	UFO (IZhO14_ufo)	C++14	80 / 100	2000 ms	41816 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 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];
}
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 S[(int)2e6], N[(int)2e6], E[(int)2e6], W[(int)2e6];
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 i = 1; i <= m; i++) {
		S[i] = n;
		N[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		E[i] = m;
		W[i] = 1;
	}
	for (int t = 1; t <= k; t++) {
		char c = get_char();
		int x = get_int(), y = get_int();
		if (c == 'S') {
			while (!a[S[x]][x] && S[x] >= 1) S[x]--;
			for (int i = S[x], done = 0, total = 0; done < r && i >= 1 && total <= 3000; i--, total++) {
				if (a[i][x] >= y) a[i][x]--, done++;
			}
		}
		else if (c == 'N') {
			while (N[x] <= n && !a[N[x]][x]) N[x]++;
			for (int i = N[x], done = 0, total = 0; done < r && i <= n && total <= 3000; i++, total++) {
				if (a[i][x] >= y) a[i][x]--, done++;
			}
		}
		else if (c == 'W') {
			while (W[x] <= m && !a[x][W[x]]) W[x]++;
			for (int i = W[x], done = 0, total = 0; done < r && i <= m && total <= 3000; i++, total++) {
				if (a[x][i] >= y) a[x][i]--, done++;
			}
		}
		else {
			while (!a[x][E[x]] && E[x] >= 1) E[x]--;
			for (int i = E[x], done = 0, total = 0; done < r && i >= 1 && total <= 3000; 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
}

Compilation message

ufo.cpp: In function 'int get(int, int)':
ufo.cpp:50:6: warning: unused variable 'res' [-Wunused-variable]
  int res = 0;
      ^

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	33268 KB	Output is correct
2	Correct	0 ms	33268 KB	Output is correct
3	Correct	0 ms	33268 KB	Output is correct
4	Correct	3 ms	33268 KB	Output is correct
5	Correct	16 ms	33540 KB	Output is correct
6	Correct	79 ms	35248 KB	Output is correct
7	Correct	909 ms	37580 KB	Output is correct
8	Correct	883 ms	37580 KB	Output is correct
9	Correct	49 ms	37384 KB	Output is correct
10	Correct	79 ms	37580 KB	Output is correct
11	Correct	39 ms	37516 KB	Output is correct
12	Correct	59 ms	37580 KB	Output is correct
13	Correct	129 ms	41816 KB	Output is correct
14	Correct	753 ms	37516 KB	Output is correct
15	Incorrect	843 ms	37580 KB	Output isn't correct
16	Correct	1239 ms	37516 KB	Output is correct
17	Execution timed out	2000 ms	41816 KB	Execution timed out
18	Execution timed out	2000 ms	41760 KB	Execution timed out
19	Incorrect	1169 ms	37972 KB	Output isn't correct
20	Correct	1099 ms	41084 KB	Output is correct