제출 #1792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1792		ainta	웜뱃 (IOI13_wombats)	C++98	76 / 100	20000 ms	54348 KiB

wombats

#include "wombats.h"
#define SZ 64
#define INF 999999999
int D[128][201][201],bucket_sz,h[5010][210],v[5010][210],TP[100][210][210],r,c;
void Do(int num,int a)
{
	int i,j,k,bsz=bucket_sz;
	if(a+bsz>r)bsz=r-a;

	for(i=0;i<=bsz;i++)
		for(j=0;j<c;j++)
			for(k=0;k<c;k++)
				TP[i][j][k]=INF;
	for(i=0;i<c;i++)TP[0][i][i]=0;
	for(i=0;i<bsz;i++)
	{
		for(j=0;j<c;j++){
			for(k=1;k<c;k++)
				if(TP[i][j][k]>TP[i][j][k-1]+h[a+i][k-1])
					TP[i][j][k]=TP[i][j][k-1]+h[a+i][k-1];
			for(k=c-2;k>=0;k--)
				if(TP[i][j][k]>TP[i][j][k+1]+h[a+i][k])
					TP[i][j][k]=TP[i][j][k+1]+h[a+i][k];
		}
		for(j=0;j<c;j++)
			for(k=0;k<c;k++)
				TP[i+1][j][k]=TP[i][j][k]+v[a+i][k];
	}
	for(i=0;i<c;i++)
		for(j=0;j<c;j++)
			D[num][i][j]=TP[bsz][i][j];
}
void Update(int a)
{
	int i,j,k,bsz=13,w[20],t;
	int c1=a*2,c2=a*2+1;
	for(i=0;i<c;i++)for(j=0;j<c;j++)D[a][i][j]=INF+1;
	for(i=0;i<c;i++){
		t=0;
		for(j=0;j<c;j+=bsz){
			for(k=0;k<c;k++)
				if(D[a][i][j]>D[c1][i][k]+D[c2][k][j])
					D[a][i][j]=D[c1][i][k]+D[c2][k][j],w[t]=k;
			t++;
		}
		w[(c-1)/bsz+1]=c-1;
		for(j=0;j<c;j++){
			if(j%bsz==0)continue;
			t=w[j/bsz+1];
			for(k=w[j/bsz];k<=t;k++)
			{
				if(D[a][i][j]>D[c1][i][k]+D[c2][k][j])
					D[a][i][j]=D[c1][i][k]+D[c2][k][j];
			}
		}
	}
}
void changeV(int P, int Q, int W)
{
	v[P][Q]=W;
	int a=P/bucket_sz;
	Do(SZ+a,a*bucket_sz);
	a+=SZ;
	while(a>1){
		a>>=1;
		Update(a);
	}
}
void changeH(int P, int Q, int W)
{
	h[P][Q]=W;
	int a=P/bucket_sz;
	Do(SZ+a,a*bucket_sz);
	a+=SZ;
	while(a>1){
		a>>=1;
		Update(a);
	}
}
int escape(int V1, int V2)
{
	return D[1][V1][V2];
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
	r=R,c=C;
	int i,j,k;
	for(i=0;i<R;i++)for(j=0;j<C-1;j++)h[i][j]=H[i][j];
	for(i=0;i<R-1;i++)for(j=0;j<C;j++)v[i][j]=V[i][j];
	bucket_sz=(R-1)/64+1;
	for(i=0;i<R;i+=bucket_sz)
	{
		Do(SZ+i/bucket_sz,i);
	}
	for(i=SZ+i/bucket_sz;i<128;i++){
		for(j=0;j<C;j++){
			for(k=0;k<C;k++)D[i][j][k]=INF;
			D[i][j][j]=0;
		}
	}
	for(i=SZ-1;i>=1;i--)Update(i);
}

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