제출 #13408

#제출 시각아이디문제언어결과실행 시간메모리
13408baneling100웜뱃 (IOI13_wombats)C++98
0 / 100
185 ms176720 KiB
#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]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...