Submission #276127

#TimeUsernameProblemLanguageResultExecution timeMemory
276127MKopchevWombats (IOI13_wombats)C++14
76 / 100
20033 ms106248 KiB
#include<bits/stdc++.h> #include"wombats.h" using namespace std; const int rmax=5e3+5,cmax=2e2+5,block_size=10,inf=1e9; int r,c,h[rmax][cmax],v[rmax][cmax]; int tree[(1<<10)+42][cmax][cmax]; int current[cmax][cmax],help[cmax][cmax]; int pref[cmax]; void make_block(int which) { for(int j=0;j<c;j++) for(int k=0;k<c;k++) if(j==k)current[j][k]=0; else current[j][k]=inf; int start=which*block_size,stop=min(r-1,which*block_size+block_size-1); for(int i=start;i<=stop;i++) { for(int j=0;j<c;j++) for(int k=0;k<c;k++) help[j][k]=inf; for(int j=0;j<c;j++) pref[j+1]=pref[j]+h[i][j]; for(int j=0;j<c;j++) for(int k=0;k<c;k++) for(int p=0;p<c;p++) { int cur=current[j][p]; cur=cur+abs(pref[p]-pref[k]); if(i!=start)cur+=v[i-1][p]; //cout<<j<<" "<<k<<" "<<p<<" -> "<<cur<<" "<<abs(pref[p]-pref[k])<<" "<<current[j][p]<<endl; help[j][k]=min(help[j][k],cur); } for(int j=0;j<c;j++) for(int k=0;k<c;k++) current[j][k]=help[j][k]; /* cout<<start<<" "<<i<<endl; for(int j=0;j<c;j++) { for(int k=0;k<c;k++)cout<<current[j][k]<<" "; cout<<endl; } cout<<"---"<<endl; */ } } int opt[cmax][cmax]; void brute(int node,int j,int k,int av) { tree[node][j][k]=inf; for(int p=0;p<c;p++) { int cur=tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k]; //cout<<"cur= "<<cur<<endl; if(tree[node][j][k]>cur) { tree[node][j][k]=cur; opt[j][k]=p; } } //cout<<"brute "<<j<<" "<<k<<" "<<opt[j][k]<<endl; } void build(int node,int l,int r,int pos) { if(l==r) { for(int j=0;j<c;j++) for(int k=0;k<c;k++) tree[node][j][k]=current[j][k]; return; } int av=(l+r)/2; if(pos<=av)build(node*2,l,av,pos); else build(node*2+1,av+1,r,pos); //opt[i][j-1]<=opt[i][j]<=opt[i+1][j] /* for(int j=0;j<c;j++) for(int k=0;k<c;k++) { tree[node][j][k]=inf; for(int p=0;p<c;p++) tree[node][j][k]=min(tree[node][j][k],tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k]); } */ memset(opt,-1,sizeof(opt)); for(int i=0;i<c;i++) { brute(node,i,0,av); brute(node,c-1,i,av); } for(int diff=-c;diff<=c;diff++) { for(int j=0;j<c;j++) { int k=j+diff; if(0<=k&&k<c&&opt[j][k]==-1) { //cout<<j<<" "<<k<<endl; assert(opt[j][k-1]!=-1&&opt[j+1][k]!=-1); tree[node][j][k]=inf; for(int p=opt[j][k-1];p<=opt[j+1][k];p++) { int cur=tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k]; if(tree[node][j][k]>cur) { tree[node][j][k]=cur; opt[j][k]=p; } } } } } } void init(int R,int C,int H[5000][200],int V[5000][200]) { r=R; c=C; for(int i=0;i<R;i++) for(int j=0;j<C-1;j++) h[i][j]=H[i][j]; for(int i=0;i<R-1;i++) for(int j=0;j<C;j++) v[i][j]=V[i][j]; for(int i=0;i*block_size<r;i++) { make_block(i); build(1,0,(r-1)/block_size,i); } } void changeH(int P,int Q,int W) { h[P][Q]=W; make_block(P/block_size); build(1,0,(r-1)/block_size,P/block_size); } void changeV(int P,int Q,int W) { v[P][Q]=W; make_block(P/block_size); build(1,0,(r-1)/block_size,P/block_size); } int escape(int V1,int V2) { return tree[1][V1][V2]; }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#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...