제출 #2482

#제출 시각아이디문제언어결과실행 시간메모리
2482kriii웜뱃 (IOI13_wombats)C++98
55 / 100
20000 ms26672 KiB
#include "wombats.h" #define group_size 500 const int NON = 0x7fffffff; int N, M, G, Start[30], End[30], Z = 32; int ANS[200][200],GO[64][200][200],OUT[64],NOW[200],LEFT[200],RIGHT[200]; int HH[5000][200],VV[5000][200]; inline int min(int a, int b){return a < b ? a : b;} void going(int i) { int j; for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j]; for (j=1;j<M;j++){ if (LEFT[j-1] == NON) continue; LEFT[j] = min(LEFT[j],LEFT[j-1]+HH[i][j-1]); } for (j=M-2;j>=0;j--){ if (RIGHT[j+1] == NON) continue; RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+HH[i][j]); } for (j=0;j<M;j++){ NOW[j] = min(NOW[j],LEFT[j]); NOW[j] = min(NOW[j],RIGHT[j]); } } void make() { int i,j; for (i=0;i<M;i++){ for (j=0;j<M;j++) NOW[j] = GO[1][i][j]; going(N-1); for (j=0;j<M;j++) ANS[i][j] = NOW[j]; } } void modify(int g) { int i,j,k,x=g+Z,s; 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++){ going(k); for (j=0;j<M;j++) NOW[j] += VV[k][j]; } for (j=0;j<M;j++) GO[x][i][j] = NOW[j]; } x /= 2; s = 1; while (x){ if (OUT[x*2] > 0 || (OUT[x*2] == 0 && OUT[x*2+1] == s)) for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = GO[x*2][i][j]; else{ for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = NON; for (i=0;i<M;i++) for (j=0;j<M;j++) for (k=0;k<M;k++) GO[x][i][j] = min(GO[x][i][j],GO[x*2][i][k]+GO[x*2+1][k][j]); } x /= 2; s *= 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-1; if (Start[G-1] == End[G-1]) G--; for (i=0;i<R;i++) for (j=0;j<C-1;j++) HH[i][j] = H[i][j]; for (i=0;i<R-1;i++) for (j=0;j<C;j++) VV[i][j] = V[i][j]; for (i=G;i<Z;i++) OUT[i+Z] = 1; for (i=Z-1;i>=1;i--) OUT[i] = OUT[i*2] + OUT[i*2+1]; for (i=0;i<G;i++) modify(i); make(); } void changeH(int P, int Q, int W) { HH[P][Q] = W; modify(P/group_size); make(); } void changeV(int P, int Q, int W) { VV[P][Q] = W; modify(P/group_size); make(); } int escape(int V1, int V2) { return ANS[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...