Submission #13427

#TimeUsernameProblemLanguageResultExecution timeMemory
13427dohyun0324Wombats (IOI13_wombats)C++98
12 / 100
448 ms194900 KiB
#include "wombats.h" #include<algorithm> using namespace std; int maxi,r,c,h[5010][210],v[5010][210],tree[1010][210][210],d[11][210][210],arr[210],top,D[11][210][210],imsi[210],t; void Merge(int x) { int i,j,k,l,w=0; x/=2; while(x){ if(x*2+1>maxi){ for(i=1;i<=c;i++){ for(j=1;j<=c;j++){ tree[x][i][j]=tree[x*2][i][j]; } } x/=2; continue; } arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ tree[x][k][k+j-1]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ if(tree[x][k][k+j-1]>tree[x*2][k][l]+tree[x*2+1][l][k+j-1]) tree[x][k][k+j-1]=tree[x*2][k][l]+tree[x*2+1][l][k+j-1], imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ tree[x][k+j-1][k]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ if(tree[x][k+j-1][k]>tree[x*2][k+j-1][l]+tree[x*2+1][l][k]) tree[x][k+j-1][k]=tree[x*2][k+j-1][l]+tree[x*2+1][l][k], imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } x/=2; } } void update(int x) { int p,i,j,k,l,w=0,s1,s2; for(i=(x-1)*10+1;i<=min(r-1,(x-1)*10+10);i++){ w++; arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ d[w][k][k+j-1]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ p=v[i][l]; if(l>=k) s1=1; else s1=-1; if(l<=k+j-1) s2=1; else s2=-1; p=v[i][l]+s2*(h[i+1][k+j-2]-h[i+1][l-1])+s1*(h[i][l-1]-h[i][k-1]); if(d[w][k][k+j-1]>p) d[w][k][k+j-1]=p, imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ d[w][k+j-1][k]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ if(l>=k+j-1) s1=-1; else s1=1; if(l>=k) s2=1; else s2=-1; p=v[i][l]+s1*(h[i][k+j-2]-h[i][l-1])+s2*(h[i+1][l-1]-h[i+1][k-1]); if(d[w][k+j-1][k]>p) d[w][k+j-1][k]=p, imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } } for(i=1;i<=c;i++){ for(j=1;j<=c;j++){ D[1][i][j]=d[1][i][j]; } } for(i=2;i<=w;i++){ arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ D[i][k][k+j-1]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ p=D[i-1][k][l]+d[i][l][k+j-1]; if(D[i][k][k+j-1]>p) D[i][k][k+j-1]=p, imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } arr[1]=1, arr[2]=c; for(j=c;j>=1;j--){ for(k=1;k<=c-j+1;k++){ D[i][k+j-1][k]=2147483647; for(l=arr[k];l<=arr[k+1];l++){ p=D[i-1][k+j-1][l]+d[i][l][k]; if(D[i][k+j-1][k]>p) D[i][k+j-1][k]=p, imsi[k]=l; } } for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1]; arr[1]=1; arr[c-j+3]=c; } } maxi=max(maxi,x+t-1); for(i=1;i<=c;i++){ for(j=1;j<=c;j++){ tree[x+t-1][i][j]=D[w][i][j]; } } Merge(x+t-1); } void init(int R, int C, int H[5000][200], int V[5000][200]) { r=R; c=C; int i,j; for(i=1;i<=r;i++){ for(j=1;j<=c-1;j++){ h[i][j]=h[i][j-1]+H[i-1][j-1]; } } for(i=1;i<=r-1;i++){ for(j=1;j<=c;j++){ v[i][j]=V[i-1][j-1]; } } for(t=1;t<(r-2)/10+1;t*=2); for(i=1;i<=(r-1)/10+1;i++) update(i); } void changeH(int P, int Q, int W) { int i,j,s; P++; Q++; s=W-(h[P][Q]-h[P][Q-1]); for(i=Q;i<=c-1;i++) h[P][i]+=s; update((P-1)/10+1); } void changeV(int P, int Q, int W) { v[P+1][Q+1]=W; update((P-1)/10+1); } int escape(int V1, int V2) { return tree[1][V1+1][V2+1]; }
#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...