| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 5190 | ainta | UFO (IZhO14_ufo) | C++98 | 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<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>>w;
int n, m, R, K, P;
int dir[2][256];
int D[4][10001][11][11];
bool ck;
void Do2(int d, int x, int h){
int i, c, t, b = -1, e = d < 2 ? m : n, pp = d % 2 ? -1 : 1, t2;
for (i = 0; i < R; i++){
t = D[d][x][h][i];
if (t == b || t == e)continue;
if (i){
t2 = D[d][x][h][i - 1];
if (t2 == b || t2 == e){
t = t2;
continue;
}
if (i && (t2 - t) * pp >= 0) t = t2 + pp;
}
if (d < 2){
while (t != b && t != e && w[x][t] < h) t += pp;
}
else{
while (t != b && t != e && w[t][x] < h) t += pp;
}
D[d][x][h][i] = t;
}
}
void Do(int d, int h, int x){
int i, c = 0, b = -1, e = d<2 ? m : n, t;
if (n <= 100 && d > 1){
if (d == 2) b = 0, e = n, t = 1;
else b = n - 1, e = -1, t = -1;
for (i = b; i != e && c < R; i += t){
if (w[i][x] >= h){
w[i][x]--;
Do2(0, i, h);
Do2(1, i, h);
c++;
}
}
return;
}
for (i = 0; i < R; i++){
t = D[d][x][h][i];
if (t == b || t == e)break;
if (d < 2){
w[x][t]--;
if (n > 100){
Do2(2, t, h);
Do2(3, t, h);
}
}
else{
w[t][x]--;
Do2(0, t, h);
Do2(1, t, h);
}
}
for (i = h; i <= 10; i++)Do2(d, x, i);
}
int main(){
int i, j, k, c, x, h, l, S;
char pp[2];
dir[0]['E'] = 1, dir[0]['S'] = 3, dir[0]['W'] = 0, dir[0]['N'] = 2;
dir[1]['S'] = 1, dir[1]['E'] = 3, dir[1]['N'] = 0, dir[1]['W'] = 2;
scanf("%d%d%d%d%d", &n, &m, &R, &K, &P);
if (n > m){
swap(n, m);
ck = true;
}
w.resize(n);
for (i = 0; i < n; i++){
w[i].resize(m);
for (j = 0; j < m; j++){
if(!ck)scanf("%d", &w[i][j]);
else scanf("%d", &w[j][i]);
}
}
for (i = 0; i < n; i++){
for (j = 1; j <= 10; j++){
c = 0;
for (k = 0; k < m && c < R; k++){
if (w[i][k] >= j)D[0][i][j][c++] = k;
}
while (c < R)D[0][i][j][c++] = m;
c = 0;
for (k = m - 1; k >= 0 && c < R; k--){
if (w[i][k] >= j)D[1][i][j][c++] = k;
}
while (c < R)D[1][i][j][c++] = -1;
}
}
if (n > 100){
for (i = 0; i < m; i++){
for (j = 1; j <= 10; j++){
c = 0;
for (k = 0; k < n && c < R; k++){
if (w[k][i] >= j)D[2][i][j][c++] = k;
}
while (c < R)D[2][i][j][c++] = m;
c = 0;
for (k = n - 1; k >= 0 && c < R; k--){
if (w[k][i] >= j)D[3][i][j][c++] = k;
}
while (c < R)D[3][i][j][c++] = -1;
}
}
}
int dirr, res = 0;
while (K--){
scanf("%s%d%d", pp, &x, &h);
x--;
dirr = dir[ck][pp[0]];
Do(dirr, h, x);
}
for (i = 0; i <= n - P; i++){
for (j = 0; j <= m - P; j++){
S = 0;
for (k = 0; k < P; k++)for (l = 0; l < P; l++)S += w[i + k][j + l];
res = max(res, S);
}
}
printf("%d\n", res);
return 0;
}