Submission #39056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
39056	2018-01-09T06:40:17 Z	RockyB	UFO (IZhO14_ufo)	C++14	60 / 100	2000 ms	17520 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];
}
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();
		}
	}
	int S[m + 1], N[m + 1], E[n + 1], W[n + 1];
	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 (!a[N[x]][x] && N[x] <= n) 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') {
			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 {
			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

60.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	63 ms	4000 KB	Output is correct
7	Correct	843 ms	6988 KB	Output is correct
8	Correct	739 ms	6988 KB	Output is correct
9	Runtime error	36 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	26 ms	6988 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	19 ms	7080 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	36 ms	6992 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	76 ms	11220 KB	Output is correct
14	Correct	779 ms	7080 KB	Output is correct
15	Incorrect	823 ms	6988 KB	Output isn't correct
16	Correct	1159 ms	7084 KB	Output is correct
17	Execution timed out	2000 ms	11224 KB	Execution timed out
18	Execution timed out	2000 ms	11324 KB	Execution timed out
19	Incorrect	1209 ms	8160 KB	Output isn't correct
20	Correct	1313 ms	17520 KB	Output is correct