oj.uz

Submission #13410

# Submission time Handle Problem Language Result Execution time Memory
13410 2015-02-18T14:45:11 Z baneling100 Wombats (IOI13_wombats) C++
100 / 100
 7459 ms 176720 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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