| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 2488 |
2013-07-22T13:14:55 Z |
kriii |
Wombats (IOI13_wombats) |
C++ |
|
11822 ms |
96676 KB |
#include "wombats.h"
#define group_size 20
const int NON = 0x0fffffff;
const int Z = 256;
int N, M, G, Start[Z], End[Z], MADE;
int ANS[200][200],GO[Z*2][200][200];
int NOW[200],LEFT[200],RIGHT[200];
int H[5001][200],V[5001][200];
inline int min(int a, int b){return a < b ? a : b;}
void modify(int g)
{
int i,j,k,x=g+Z,s,p;
if (g >= G){
for (i=0;i<M;i++){
for (j=0;j<M;j++){
GO[x][i][j] = i == j ? 0 : NON;
}
}
}
else{
for (i=0;i<M;i++){
for (j=0;j<M;j++) NOW[j] = NON;
NOW[i] = 0;
for (k=Start[g];k<End[g];k++){
for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j];
for (j=1;j<M;j++) LEFT[j] = min(LEFT[j],LEFT[j-1]+H[k][j-1]);
for (j=M-2;j>=0;j--) RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+H[k][j]);
for (j=0;j<M;j++) NOW[j] = min(NOW[j],min(LEFT[j],RIGHT[j]));
for (j=0;j<M;j++) NOW[j] += V[k][j];
}
for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
}
}
x /= 2;
while (x){
NOW[0] = 0; NOW[1] = M-1;
for (i=M-1;i>=0;i--){
for (j=M-1;j>=i;j--){
s = NON; p = NOW[j-i];
for (k=NOW[j-i];k<=NOW[j-i+1];k++){
int &a = GO[x*2][j-i][k];
int &b = GO[x*2+1][k][j];
if (s >= a + b){
s = a + b;
p = k;
}
}
GO[x][j-i][j] = s;
NOW[j-i+1] = p;
}
NOW[M-i+1] = M-1;
}
NOW[0] = 0; NOW[1] = M-1;
for (i=M-1;i>=0;i--){
for (j=M-1;j>=i;j--){
s = NON; p = NOW[j-i];
for (k=NOW[j-i];k<=NOW[j-i+1];k++){
int &a = GO[x*2][j][k];
int &b = GO[x*2+1][k][j-i];
if (s >= a + b){
s = a + b;
p = k;
}
}
GO[x][j][j-i] = s;
NOW[j-i+1] = p;
}
NOW[M-i+1] = M-1;
}
x /= 2;
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
N = R; M = C;
G = (R + group_size - 1) / group_size; int i,j;
for (i=0;i<G;i++){
Start[i] = i * group_size;
End[i] = (i + 1) * group_size;
}
if (End[G-1] >= R) End[G-1] = R;
if (Start[G-1] == End[G-1]) G--;
for (i=0;i<R;i++) for (j=0;j<C-1;j++) ::H[i][j] = H[i][j];
for (i=0;i<R-1;i++) for (j=0;j<C;j++) ::V[i][j] = V[i][j];
for (i=0;i<Z;i++) modify(i);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
modify(P/group_size);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
modify(P/group_size);
}
int escape(int V1, int V2) {
return GO[1][V1][V2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
3 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
100 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 5 |
Correct |
2 ms |
96676 KB |
Output is correct |
| 6 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 7 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 8 |
Correct |
0 ms |
96676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
8 ms |
96676 KB |
Output is correct |
| 5 |
Correct |
7 ms |
96676 KB |
Output is correct |
| 6 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 7 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 8 |
Correct |
10 ms |
96676 KB |
Output is correct |
| 9 |
Correct |
9 ms |
96676 KB |
Output is correct |
| 10 |
Correct |
11 ms |
96676 KB |
Output is correct |
| 11 |
Correct |
112 ms |
96676 KB |
Output is correct |
| 12 |
Correct |
16 ms |
96676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
705 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
628 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
638 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
642 ms |
96676 KB |
Output is correct |
| 5 |
Correct |
634 ms |
96676 KB |
Output is correct |
| 6 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 7 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 8 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 9 |
Correct |
2119 ms |
96676 KB |
Output is correct |
| 10 |
Correct |
1 ms |
96676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
4 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
5 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
47 ms |
96676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
629 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
622 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
639 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
639 ms |
96676 KB |
Output is correct |
| 5 |
Correct |
635 ms |
96676 KB |
Output is correct |
| 6 |
Correct |
5 ms |
96676 KB |
Output is correct |
| 7 |
Correct |
2 ms |
96676 KB |
Output is correct |
| 8 |
Correct |
6 ms |
96676 KB |
Output is correct |
| 9 |
Correct |
50 ms |
96676 KB |
Output is correct |
| 10 |
Correct |
1 ms |
96676 KB |
Output is correct |
| 11 |
Correct |
1 ms |
96676 KB |
Output is correct |
| 12 |
Correct |
87 ms |
96676 KB |
Output is correct |
| 13 |
Correct |
1 ms |
96676 KB |
Output is correct |
| 14 |
Correct |
1 ms |
96676 KB |
Output is correct |
| 15 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 16 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 17 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 18 |
Correct |
15 ms |
96676 KB |
Output is correct |
| 19 |
Correct |
14 ms |
96676 KB |
Output is correct |
| 20 |
Correct |
11 ms |
96676 KB |
Output is correct |
| 21 |
Correct |
13 ms |
96676 KB |
Output is correct |
| 22 |
Correct |
10 ms |
96676 KB |
Output is correct |
| 23 |
Correct |
11 ms |
96676 KB |
Output is correct |
| 24 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 25 |
Correct |
90 ms |
96676 KB |
Output is correct |
| 26 |
Correct |
13 ms |
96676 KB |
Output is correct |
| 27 |
Correct |
2563 ms |
96676 KB |
Output is correct |
| 28 |
Correct |
3511 ms |
96676 KB |
Output is correct |
| 29 |
Correct |
2832 ms |
96676 KB |
Output is correct |
| 30 |
Correct |
2996 ms |
96676 KB |
Output is correct |
| 31 |
Correct |
3286 ms |
96676 KB |
Output is correct |
| 32 |
Correct |
0 ms |
96676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
624 ms |
96676 KB |
Output is correct |
| 2 |
Correct |
759 ms |
96676 KB |
Output is correct |
| 3 |
Correct |
671 ms |
96676 KB |
Output is correct |
| 4 |
Correct |
640 ms |
96676 KB |
Output is correct |
| 5 |
Correct |
607 ms |
96676 KB |
Output is correct |
| 6 |
Correct |
5 ms |
96676 KB |
Output is correct |
| 7 |
Correct |
7 ms |
96676 KB |
Output is correct |
| 8 |
Correct |
3 ms |
96676 KB |
Output is correct |
| 9 |
Correct |
46 ms |
96676 KB |
Output is correct |
| 10 |
Correct |
3 ms |
96676 KB |
Output is correct |
| 11 |
Correct |
4 ms |
96676 KB |
Output is correct |
| 12 |
Correct |
84 ms |
96676 KB |
Output is correct |
| 13 |
Correct |
1 ms |
96676 KB |
Output is correct |
| 14 |
Correct |
2 ms |
96676 KB |
Output is correct |
| 15 |
Correct |
4104 ms |
96676 KB |
Output is correct |
| 16 |
Correct |
11822 ms |
96676 KB |
Output is correct |
| 17 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 18 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 19 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 20 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 21 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 22 |
Correct |
8 ms |
96676 KB |
Output is correct |
| 23 |
Correct |
13 ms |
96676 KB |
Output is correct |
| 24 |
Correct |
13 ms |
96676 KB |
Output is correct |
| 25 |
Correct |
9 ms |
96676 KB |
Output is correct |
| 26 |
Correct |
13 ms |
96676 KB |
Output is correct |
| 27 |
Correct |
93 ms |
96676 KB |
Output is correct |
| 28 |
Correct |
12 ms |
96676 KB |
Output is correct |
| 29 |
Correct |
2097 ms |
96676 KB |
Output is correct |
| 30 |
Correct |
3385 ms |
96676 KB |
Output is correct |
| 31 |
Correct |
11777 ms |
96676 KB |
Output is correct |
| 32 |
Correct |
11370 ms |
96676 KB |
Output is correct |
| 33 |
Correct |
2886 ms |
96676 KB |
Output is correct |
| 34 |
Correct |
11118 ms |
96676 KB |
Output is correct |
| 35 |
Correct |
2870 ms |
96676 KB |
Output is correct |
| 36 |
Correct |
11172 ms |
96676 KB |
Output is correct |
| 37 |
Correct |
3004 ms |
96676 KB |
Output is correct |
| 38 |
Correct |
11413 ms |
96676 KB |
Output is correct |
| 39 |
Correct |
0 ms |
96676 KB |
Output is correct |
| 40 |
Correct |
11450 ms |
96676 KB |
Output is correct |
