| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 338022 | boykut | UFO (IZhO14_ufo) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, r, p;
cin >> n >> m >> r >> k >> p;
int a[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < k; i++) {
char ch; cin >> ch;
int pos, h; cin >> pos >> h;
pos--;
if (ch == 'N') {
int cnt = 0;
for (int i = 0; i < n && cnt < r; i++) {
if (a[i][pos] >= h) {
a[i][pos] --;
cnt++;
if (cnt == r) break;
}
}
} else if (ch == 'E') {
int cnt = 0;
for (int i = m - 1; i >= 0 && cnt < r; i--) {
if (a[pos][i] >= h) {
a[pos][i] --;
cnt++;
if (cnt == r) break;
}
}
} else if (ch == 'W') {
int cnt = 0;
for (int i = 0; i < m && cnt < r; i++) {
if (a[pos][i] >= h) {
a[pos][i] --;
cnt++;
if (cnt == r) break;
}
}
} else {
int cnt = 0;
for (int i = n - 1; i >= 0 && cnt < r; i--) {
if (a[i][pos] >= h) {
a[i][pos] --;
cnt++;
if (cnt == r) break;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << a[i][j] << ' ';
}
//cout << '\n';
}
int sp[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int A = (i?sp[i-1][j]:0);
int B = (j?sp[i][j-1]:0);
int C = (i&&j?sp[i-1][j-1]:0);
sp[i][j]=a[i][j]+A+B-C;
}
}
auto get = [&sp](int i1, int j1, int i2, int j2) -> int {
int A = sp[i2][j2];
int B = (i1?sp[i1-1][j2]:0);
int C = (j1?sp[i2][j1-1]:0);
int D = (i1&&j1?sp[i1-1][j1-1]:0);
return A-B-C+D;
};
int sum = 0, ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i + p <= n && j + p <= m) {
sum = get(i, j, i+p, j+p);
if (sum > ans) {
//cout << i << ' ' << j << '\n';
ans = sum;
//cout << sum << "\n\n";
}
}
}
}
cout << ans << '\n';
return 0;
}