Submission #126152

#TimeUsernameProblemLanguageResultExecution timeMemory
126152nxteruWombats (IOI13_wombats)C++14
100 / 100
8122 ms98728 KiB
#include "wombats.h" #include <bits/stdc++.h> using namespace std; #define INF 1000000001 #define B 20 struct node{ int n,d[200][200]; void ini(int x){ n=x; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j)d[i][j]=0; else d[i][j]=INF; } } } node plus(node &q){ node res; res.ini(n); int a[205][205],s; for(int i=n-1;i>-n;i--){ for(int j=max(-i,0);i+j<n&&j<n;j++){ s=INF; int x,y; if(j-1>=0)x=a[i+j][j-1]; else x=0; if(i+j+1<n)y=a[i+j+1][j]; else y=n-1; for(int k=x;k<=y;k++){ if(d[i+j][k]+q.d[k][j]<s){ x=k; s=d[i+j][k]+q.d[k][j]; } } a[i+j][j]=x; res.d[i+j][j]=min(s,INF); } } return res; } }; struct SEG{ int n; node seg[1<<9]; void ini(int x){ n=x; for(int i=0;i<1<<9;i++)seg[i].ini(n); } void up(int a,node &q){ a+=(1<<8)-1; seg[a]=q; while(a>0){ a=(a-1)/2; seg[a]=seg[a*2+1].plus(seg[a*2+2]); } } }; int h[5005][205],w[5005][205],n,m,p[205][205]; SEG s; void change(int x){ x=x/B; for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ if(i==j)p[i][j]=0; else p[i][j]=INF; } } for(int i=0;i<B&&x*B+i<n;i++){ for(int j=0;j<m;j++){ int *q=p[j]; for(int k=1;k<m;k++)q[k]=min(q[k],q[k-1]+h[x*B+i][k-1]); for(int k=m-2;k>=0;k--)q[k]=min(q[k],q[k+1]+h[x*B+i][k]); for(int k=0;k<m;k++)q[k]+=w[x*B+i][k]; } } node res; res.n=m; for(int i=0;i<m;i++)for(int j=0;j<m;j++)res.d[i][j]=p[i][j]; s.up(x,res); } void init(int R, int C, int H[5000][200], int V[5000][200]) { n=R,m=C; s.ini(m); for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)h[i][j]=H[i][j]; for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)w[i][j]=V[i][j]; for(int i=0;i<n;i+=B)change(i); } void changeH(int a, int b, int x) { h[a][b]=x; change(a); } void changeV(int a, int b, int x) { w[a][b]=x; change(a); } int escape(int a, int b) { return s.seg[0].d[a][b]; }

Compilation message (stderr)

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