Submission #64534

#	Time	Username	Problem	Language	Result	Execution time	Memory
64534		TadijaSebez	Wombats (IOI13_wombats)	C++11	100 / 100	6521 ms	228552 KiB

wombats

#include "wombats.h"
#include <stdio.h>
const int N=5050;
const int M=2048;
const int H=205;
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
int n,m,dp[M][H][H],ls[M],rs[M],x[N][M],y[N][M],tsz,root,opt[H];
void Take(int c)
{
	int i,j,k,l,r;
	for(i=0;i<m;i++) opt[i]=0;
	for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
	for(i=m-1;i>-m;i--)
	{
		for(j=min(m-1,m-i-1);j+min(i,0)>=0;j--)
		{
			if(j==max(-i,0)) l=0;
			else l=opt[j-1];
			if(j==min(m-1,m-i-1)) r=m-1;
			else r=opt[j];
			for(k=l;k<=r;k++)
			{
				if(dp[c][j][j+i]>dp[ls[c]][j][k]+dp[rs[c]][k][j+i])
				{
					dp[c][j][j+i]=dp[ls[c]][j][k]+dp[rs[c]][k][j+i];
					opt[j]=k;
				}
			}
		}
	}
}
void Make(int c, int ss, int se)
{
	int i,j,k;
	for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]=inf;
	for(i=0;i<m;i++) dp[c][i][i]=0;
	for(k=ss;k<=se;k++)
	{
		for(i=0;i<m;i++)
		{
			for(j=1;j<m;j++) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j-1]+x[k][j-1]);
			for(j=m-2;~j;j--) dp[c][i][j]=min(dp[c][i][j],dp[c][i][j+1]+x[k][j]);
		}
		for(i=0;i<m;i++) for(j=0;j<m;j++) dp[c][i][j]+=y[k][j];
	}
}
void Build(int &c, int ss, int se)
{
	c=++tsz;
	if(se-ss+1<=10)
	{
		Make(c,ss,se);
		return;
	}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	Take(c);
}
void Upd(int c, int ss, int se, int qi)
{
	if(se-ss+1<=10)
	{
		Make(c,ss,se);
		return;
	}
	int mid=ss+se>>1;
	if(qi<=mid) Upd(ls[c],ss,mid,qi);
	else Upd(rs[c],mid+1,se,qi);
	Take(c);
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
	n=R;m=C;
	int i,j;
	for(i=0;i<n;i++) for(j=0;j<m-1;j++) x[i][j]=H[i][j];
	for(i=0;i<n-1;i++) for(j=0;j<m;j++) y[i][j]=V[i][j];
	Build(root,0,n-1);
}
void changeH(int p, int q, int w){ x[p][q]=w;Upd(root,0,n-1,p);}
void changeV(int p, int q, int w){ y[p][q]=w;Upd(root,0,n-1,p);}
int escape(int a, int b){ return dp[root][a][b];}
//------------------//
/*
int _V[5000][200],_H[5000][200];
int main()
{
	int R,C,i,j,Q,p,q,w,a,b,t;
	scanf("%i %i",&R,&C);
	for(i=0;i<R;i++) for(j=0;j<C-1;j++) scanf("%i",&_H[i][j]);
	for(i=0;i<R-1;i++) for(j=0;j<C;j++) scanf("%i",&_V[i][j]);
	init(R,C,_H,_V);
	scanf("%i",&Q);
	while(Q--)
	{
		scanf("%i",&t);
		if(t==1)
		{
			scanf("%i %i %i",&p,&q,&w);
			changeH(p,q,w);
		}
		if(t==2)
		{
			scanf("%i %i %i",&p,&q,&w);
			changeV(p,q,w);
		}
		if(t==3)
		{
			scanf("%i %i",&a,&b);
			printf("%i\n",escape(a,b));
		}
	}
	return 0;
}
*/
//------------------//

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;
      ^~~
wombats.cpp: In function 'void Build(int&, int, int)':
wombats.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wombats.cpp: In function 'void Upd(int, int, int, int)':
wombats.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24