/// 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 (!a[x][W[x]] && W[x] <= m) 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 {
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;
^
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
33268 KB |
Output is correct |
| 5 |
Correct |
16 ms |
33540 KB |
Output is correct |
| 6 |
Correct |
43 ms |
35248 KB |
Output is correct |
| 7 |
Correct |
789 ms |
37580 KB |
Output is correct |
| 8 |
Correct |
816 ms |
37580 KB |
Output is correct |
| 9 |
Incorrect |
769 ms |
37384 KB |
Output isn't correct |
| 10 |
Correct |
759 ms |
37580 KB |
Output is correct |
| 11 |
Incorrect |
766 ms |
37516 KB |
Output isn't correct |
| 12 |
Correct |
799 ms |
37580 KB |
Output is correct |
| 13 |
Correct |
99 ms |
41816 KB |
Output is correct |
| 14 |
Correct |
783 ms |
37516 KB |
Output is correct |
| 15 |
Incorrect |
789 ms |
37580 KB |
Output isn't correct |
| 16 |
Correct |
1086 ms |
37516 KB |
Output is correct |
| 17 |
Execution timed out |
2000 ms |
41816 KB |
Execution timed out |
| 18 |
Correct |
1933 ms |
41760 KB |
Output is correct |
| 19 |
Incorrect |
1079 ms |
37972 KB |
Output isn't correct |
| 20 |
Correct |
1129 ms |
41084 KB |
Output is correct |
