Submission #13410

#	Time	Username	Problem	Language	Result	Execution time	Memory
13410		baneling100	Wombats (IOI13_wombats)	C++98	100 / 100	7459 ms	176720 KiB

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24