| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5191 |
2014-02-14T04:26:07 Z |
ainta |
UFO (IZhO14_ufo) |
C++ |
|
333 ms |
24764 KB |
#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;
}
Compilation message
ufo.cpp: In function 'void Do2(int, int, int)':
ufo.cpp:11:9: warning: unused variable 'c' [-Wunused-variable]
int i, c, t, b = -1, e = d < 2 ? m : n, pp = d % 2 ? -1 : 1, t2;
^
ufo.cpp: In function 'int main()':
ufo.cpp:117:23: warning: array subscript has type 'char' [-Wchar-subscripts]
dirr = dir[ck][pp[0]];
^
ufo.cpp:70:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &n, &m, &R, &K, &P);
^
ufo.cpp:79:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if(!ck)scanf("%d", &w[i][j]);
^
ufo.cpp:80:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
else scanf("%d", &w[j][i]);
^
ufo.cpp:115:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d%d", pp, &x, &h);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
20844 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
20844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
0 ms |
20844 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
20844 KB |
Output isn't correct |
| 5 |
Correct |
69 ms |
21116 KB |
Output is correct |
| 6 |
Incorrect |
193 ms |
22824 KB |
Output isn't correct |
| 7 |
Runtime error |
143 ms |
24764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
106 ms |
24764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Correct |
333 ms |
24764 KB |
Output is correct |
| 10 |
Correct |
323 ms |
24764 KB |
Output is correct |
| 11 |
Correct |
273 ms |
24620 KB |
Output is correct |
| 12 |
Correct |
306 ms |
24764 KB |
Output is correct |
| 13 |
Runtime error |
0 ms |
21236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Correct |
263 ms |
24620 KB |
Output is correct |
| 15 |
Runtime error |
113 ms |
24764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
96 ms |
24620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
0 ms |
21236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
0 ms |
21316 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Incorrect |
196 ms |
24764 KB |
Output isn't correct |
| 20 |
Correct |
176 ms |
24752 KB |
Output is correct |
