Submission #126090

#TimeUsernameProblemLanguageResultExecution timeMemory
126090nxteruWombats (IOI13_wombats)C++14
12 / 100
319 ms262144 KiB
#include "wombats.h" #include <bits/stdc++.h> using namespace std; #define INF 1000000001 struct node{ int n,d[100][100]; 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[105][105]; for(int i=n-1;i>-n;i--){ for(int j=max(-i,0);i+j<n&&j<n;j++){ 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]<d[i+j][x]+q.d[x][j])x=k; a[i+j][j]=x; res.d[i+j][j]=min(d[i+j][x]+q.d[x][j],INF); } } return res; } }; struct SEG{ int n; node seg[1<<14]; void ini(int x){ n=x; for(int i=0;i<1<<14;i++)seg[i].ini(n); } void up(int a,node &q){ a+=(1<<13)-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]; SEG s; void change(int x){ p[0]=0; for(int i=1;i<m;i++)p[i]=p[i-1]+h[x][i-1]; node res; res.ini(m); for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ res.d[i][j]=p[max(i,j)]-p[min(i,j)]+w[x][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++)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...