답안 #13410 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13410	2015-02-18T14:45:11 Z	baneling100	웜뱃 (IOI13_wombats)	C++	100 / 100	7459 ms	176720 KB

wombats

#include "wombats.h"
#include <algorithm>
#define N_MAX 512
#define R_MAX 5000
#define C_MAX 200
#define B_SIZE 10
#define INF 999999999

using namespace std;

int R, C, H[R_MAX][C_MAX], V[R_MAX][C_MAX], X[C_MAX], Y[C_MAX];
int B, N, Idx[N_MAX<<1][C_MAX][C_MAX], D[B_SIZE+1][C_MAX];

void makeTerminal(int K) {

    int i, j, k, U=(K-N)*B_SIZE;

    for(k=0 ; k<C ; k++) {
        for(i=0 ; i<B_SIZE ; i++) for(j=0 ; j<C ; j++) D[i][j]=INF;
        D[0][k]=0;
        for(i=0 ; i<B_SIZE ; i++) {
            for(j=1 ; j<C ; j++) D[i][j]=min(D[i][j],D[i][j-1]+H[U+i][j-1]);
            for(j=C-2 ; j>=0 ; j--) D[i][j]=min(D[i][j],D[i][j+1]+H[U+i][j]);
            for(j=0 ; j<C ; j++) D[i+1][j]=D[i][j]+V[U+i][j];
        }
        for(i=0 ; i<C ; i++) Idx[K][k][i]=D[B_SIZE][i];
    }
}

void makeInterior(int K) {

    int i, j, k, P, Q, Min, Num;

    for(i=0 ; i<C ; i++) {
        P=0, Q=C-1-i, X[i]=C-1, k=0, Min=INF+1;
        for(j=0 ; k<=i ; j++) {
            if(Min>Idx[K<<1][P][j]+Idx[(K<<1)+1][j][Q]) {
                Min=Idx[K<<1][P][j]+Idx[(K<<1)+1][j][Q];
                Num=j;
            }
            if(j==X[k]) {
                Idx[K][P][Q]=Min, Y[k]=Num;
                j--, k++, P++, Q++, Min=INF+1;
            }
        }
        for(j=0 ; j<=i ; j++) X[j]=Y[j];
    }
    for(i=0 ; i<C-1 ; i++) {
        P=C-1-i, Q=0, X[i]=C-1, k=0, Min=INF+1;
        for(j=0 ; k<=i ; j++) {
            if(Min>Idx[K<<1][P][j]+Idx[(K<<1)+1][j][Q]) {
                Min=Idx[K<<1][P][j]+Idx[(K<<1)+1][j][Q];
                Num=j;
            }
            if(j==X[k]) {
                Idx[K][P][Q]=Min, Y[k]=Num;
                j--, k++, P++, Q++, Min=INF+1;
            }
        }
        for(j=0 ; j<=i ; j++) X[j]=Y[j];
    }
}

void init(int R_, int C_, int H_[R_MAX][C_MAX], int V_[R_MAX][C_MAX]) {

    int i, j, k;

    R=R_, C=C_, B=(R-1)/B_SIZE+1;
    for(N=1 ; N<B ; N<<=1);
    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=R ; i<B*B_SIZE ; i++) for(j=0 ; j<C-1 ; j++) H[i][j]=INF;
    for(i=N ; i<N+B ; i++) makeTerminal(i);
    for(i=N+B ; i<(N<<1) ; i++) for(j=0 ; j<C ; j++) {
        for(k=0 ; k<C ; k++) Idx[i][j][k]=INF;
        Idx[i][j][j]=0;
    }
    for(i=N-1 ; i>=1 ; i--) makeInterior(i);
}

void changeH(int P, int Q, int W) {

    int K=N+P/B_SIZE;

    H[P][Q]=W;
    makeTerminal(K);
    K>>=1;
    while(K) {
        makeInterior(K);
        K>>=1;
    }
}

void changeV(int P, int Q, int W) {

    int K=N+P/B_SIZE;

    V[P][Q]=W;
    makeTerminal(K);
    K>>=1;
    while(K) {
        makeInterior(K);
        K>>=1;
    }
}

int escape(int V1, int V2) {

    return Idx[1][V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	176720 KB	Output is correct - 505 tokens
2	Correct	0 ms	176720 KB	Output is correct - 505 tokens
3	Correct	20 ms	176720 KB	Output is correct - 200005 tokens
4	Correct	0 ms	176720 KB	Output is correct - 505 tokens
5	Correct	0 ms	176720 KB	Output is correct - 505 tokens
6	Correct	0 ms	176720 KB	Output is correct - 6 tokens
7	Correct	0 ms	176720 KB	Output is correct - 6 tokens
8	Correct	0 ms	176720 KB	Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	176720 KB	Output is correct - 6 tokens
2	Correct	0 ms	176720 KB	Output is correct - 6 tokens
3	Correct	0 ms	176720 KB	Output is correct - 6 tokens
4	Correct	1 ms	176720 KB	Output is correct - 405 tokens
5	Correct	0 ms	176720 KB	Output is correct - 405 tokens
6	Correct	2 ms	176720 KB	Output is correct - 405 tokens
7	Correct	0 ms	176720 KB	Output is correct - 405 tokens
8	Correct	0 ms	176720 KB	Output is correct - 366 tokens
9	Correct	0 ms	176720 KB	Output is correct - 405 tokens
10	Correct	0 ms	176720 KB	Output is correct - 366 tokens
11	Correct	87 ms	176720 KB	Output is correct - 200005 tokens
12	Correct	0 ms	176720 KB	Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	176720 KB	Output is correct - 105 tokens
2	Correct	172 ms	176720 KB	Output is correct - 105 tokens
3	Correct	189 ms	176720 KB	Output is correct - 105 tokens
4	Correct	186 ms	176720 KB	Output is correct - 105 tokens
5	Correct	187 ms	176720 KB	Output is correct - 105 tokens
6	Correct	1 ms	176720 KB	Output is correct - 6 tokens
7	Correct	0 ms	176720 KB	Output is correct - 6 tokens
8	Correct	0 ms	176720 KB	Output is correct - 6 tokens
9	Correct	811 ms	176720 KB	Output is correct - 105 tokens
10	Correct	0 ms	176720 KB	Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	176720 KB	Output is correct - 1005 tokens
2	Correct	4 ms	176720 KB	Output is correct - 1005 tokens
3	Correct	0 ms	176720 KB	Output is correct - 1005 tokens
4	Correct	26 ms	176720 KB	Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	184 ms	176720 KB	Output is correct - 105 tokens
2	Correct	168 ms	176720 KB	Output is correct - 105 tokens
3	Correct	187 ms	176720 KB	Output is correct - 105 tokens
4	Correct	184 ms	176720 KB	Output is correct - 105 tokens
5	Correct	182 ms	176720 KB	Output is correct - 105 tokens
6	Correct	4 ms	176720 KB	Output is correct - 1005 tokens
7	Correct	4 ms	176720 KB	Output is correct - 1005 tokens
8	Correct	0 ms	176720 KB	Output is correct - 1005 tokens
9	Correct	44 ms	176720 KB	Output is correct - 100005 tokens
10	Correct	0 ms	176720 KB	Output is correct - 505 tokens
11	Correct	4 ms	176720 KB	Output is correct - 505 tokens
12	Correct	45 ms	176720 KB	Output is correct - 200005 tokens
13	Correct	0 ms	176720 KB	Output is correct - 505 tokens
14	Correct	0 ms	176720 KB	Output is correct - 505 tokens
15	Correct	0 ms	176720 KB	Output is correct - 6 tokens
16	Correct	0 ms	176720 KB	Output is correct - 6 tokens
17	Correct	0 ms	176720 KB	Output is correct - 6 tokens
18	Correct	0 ms	176720 KB	Output is correct - 405 tokens
19	Correct	0 ms	176720 KB	Output is correct - 405 tokens
20	Correct	0 ms	176720 KB	Output is correct - 405 tokens
21	Correct	0 ms	176720 KB	Output is correct - 405 tokens
22	Correct	0 ms	176720 KB	Output is correct - 366 tokens
23	Correct	0 ms	176720 KB	Output is correct - 405 tokens
24	Correct	0 ms	176720 KB	Output is correct - 366 tokens
25	Correct	90 ms	176720 KB	Output is correct - 200005 tokens
26	Correct	0 ms	176720 KB	Output is correct - 405 tokens
27	Correct	812 ms	176720 KB	Output is correct - 105 tokens
28	Correct	1862 ms	176720 KB	Output is correct - 50005 tokens
29	Correct	1843 ms	176720 KB	Output is correct - 50005 tokens
30	Correct	1903 ms	176720 KB	Output is correct - 50005 tokens
31	Correct	1957 ms	176720 KB	Output is correct - 200005 tokens
32	Correct	0 ms	176720 KB	Output is correct - 8 tokens

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	181 ms	176720 KB	Output is correct - 105 tokens
2	Correct	168 ms	176720 KB	Output is correct - 105 tokens
3	Correct	185 ms	176720 KB	Output is correct - 105 tokens
4	Correct	190 ms	176720 KB	Output is correct - 105 tokens
5	Correct	177 ms	176720 KB	Output is correct - 105 tokens
6	Correct	4 ms	176720 KB	Output is correct - 1005 tokens
7	Correct	0 ms	176720 KB	Output is correct - 1005 tokens
8	Correct	0 ms	176720 KB	Output is correct - 1005 tokens
9	Correct	27 ms	176720 KB	Output is correct - 100005 tokens
10	Correct	0 ms	176720 KB	Output is correct - 505 tokens
11	Correct	8 ms	176720 KB	Output is correct - 505 tokens
12	Correct	74 ms	176720 KB	Output is correct - 200005 tokens
13	Correct	0 ms	176720 KB	Output is correct - 505 tokens
14	Correct	0 ms	176720 KB	Output is correct - 505 tokens
15	Correct	2816 ms	176720 KB	Output is correct - 11 tokens
16	Correct	7459 ms	176720 KB	Output is correct - 200005 tokens
17	Correct	0 ms	176720 KB	Output is correct - 6 tokens
18	Correct	0 ms	176720 KB	Output is correct - 6 tokens
19	Correct	0 ms	176720 KB	Output is correct - 6 tokens
20	Correct	0 ms	176720 KB	Output is correct - 405 tokens
21	Correct	0 ms	176720 KB	Output is correct - 405 tokens
22	Correct	0 ms	176720 KB	Output is correct - 405 tokens
23	Correct	0 ms	176720 KB	Output is correct - 405 tokens
24	Correct	0 ms	176720 KB	Output is correct - 366 tokens
25	Correct	0 ms	176720 KB	Output is correct - 405 tokens
26	Correct	0 ms	176720 KB	Output is correct - 366 tokens
27	Correct	93 ms	176720 KB	Output is correct - 200005 tokens
28	Correct	0 ms	176720 KB	Output is correct - 405 tokens
29	Correct	812 ms	176720 KB	Output is correct - 105 tokens
30	Correct	1882 ms	176720 KB	Output is correct - 50005 tokens
31	Correct	7126 ms	176720 KB	Output is correct - 100005 tokens
32	Correct	7170 ms	176720 KB	Output is correct - 100005 tokens
33	Correct	1863 ms	176720 KB	Output is correct - 50005 tokens
34	Correct	7049 ms	176720 KB	Output is correct - 100005 tokens
35	Correct	1904 ms	176720 KB	Output is correct - 50005 tokens
36	Correct	7114 ms	176720 KB	Output is correct - 100005 tokens
37	Correct	1950 ms	176720 KB	Output is correct - 200005 tokens
38	Correct	7230 ms	176720 KB	Output is correct - 200005 tokens
39	Correct	0 ms	176720 KB	Output is correct - 8 tokens
40	Correct	7421 ms	176720 KB	Output is correct - 100005 tokens

답안 #13410

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 24.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
24.0 / 24.0