답안 #2471 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2471	2013-07-22T07:56:09 Z	ainta	웜뱃 (IOI13_wombats)	C++	76 / 100	20000 ms	54348 KB

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.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	54348 KB	Output is correct
2	Correct	2 ms	54348 KB	Output is correct
3	Correct	107 ms	54348 KB	Output is correct
4	Correct	1 ms	54348 KB	Output is correct
5	Correct	1 ms	54348 KB	Output is correct
6	Correct	0 ms	54348 KB	Output is correct
7	Correct	0 ms	54348 KB	Output is correct
8	Correct	0 ms	54348 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	54348 KB	Output is correct
2	Correct	0 ms	54348 KB	Output is correct
3	Correct	0 ms	54348 KB	Output is correct
4	Correct	0 ms	54348 KB	Output is correct
5	Correct	0 ms	54348 KB	Output is correct
6	Correct	1 ms	54348 KB	Output is correct
7	Correct	1 ms	54348 KB	Output is correct
8	Correct	1 ms	54348 KB	Output is correct
9	Correct	0 ms	54348 KB	Output is correct
10	Correct	1 ms	54348 KB	Output is correct
11	Correct	100 ms	54348 KB	Output is correct
12	Correct	1 ms	54348 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	386 ms	54348 KB	Output is correct
2	Correct	303 ms	54348 KB	Output is correct
3	Correct	389 ms	54348 KB	Output is correct
4	Correct	383 ms	54348 KB	Output is correct
5	Correct	381 ms	54348 KB	Output is correct
6	Correct	0 ms	54348 KB	Output is correct
7	Correct	0 ms	54348 KB	Output is correct
8	Correct	0 ms	54348 KB	Output is correct
9	Correct	1268 ms	54348 KB	Output is correct
10	Correct	0 ms	54348 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	54348 KB	Output is correct
2	Correct	5 ms	54348 KB	Output is correct
3	Correct	6 ms	54348 KB	Output is correct
4	Correct	46 ms	54348 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	459 ms	54348 KB	Output is correct
2	Correct	305 ms	54348 KB	Output is correct
3	Correct	389 ms	54348 KB	Output is correct
4	Correct	450 ms	54348 KB	Output is correct
5	Correct	370 ms	54348 KB	Output is correct
6	Correct	3 ms	54348 KB	Output is correct
7	Correct	5 ms	54348 KB	Output is correct
8	Correct	6 ms	54348 KB	Output is correct
9	Correct	46 ms	54348 KB	Output is correct
10	Correct	2 ms	54348 KB	Output is correct
11	Correct	0 ms	54348 KB	Output is correct
12	Correct	98 ms	54348 KB	Output is correct
13	Correct	3 ms	54348 KB	Output is correct
14	Correct	1 ms	54348 KB	Output is correct
15	Correct	0 ms	54348 KB	Output is correct
16	Correct	0 ms	54348 KB	Output is correct
17	Correct	0 ms	54348 KB	Output is correct
18	Correct	0 ms	54348 KB	Output is correct
19	Correct	1 ms	54348 KB	Output is correct
20	Correct	1 ms	54348 KB	Output is correct
21	Correct	0 ms	54348 KB	Output is correct
22	Correct	1 ms	54348 KB	Output is correct
23	Correct	0 ms	54348 KB	Output is correct
24	Correct	0 ms	54348 KB	Output is correct
25	Correct	81 ms	54348 KB	Output is correct
26	Correct	2 ms	54348 KB	Output is correct
27	Correct	1267 ms	54348 KB	Output is correct
28	Correct	5538 ms	54348 KB	Output is correct
29	Correct	4355 ms	54348 KB	Output is correct
30	Correct	5076 ms	54348 KB	Output is correct
31	Correct	5507 ms	54348 KB	Output is correct
32	Correct	0 ms	54348 KB	Output is correct

Subtask #6
0.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	386 ms	54348 KB	Output is correct
2	Correct	306 ms	54348 KB	Output is correct
3	Correct	455 ms	54348 KB	Output is correct
4	Correct	475 ms	54348 KB	Output is correct
5	Correct	378 ms	54348 KB	Output is correct
6	Correct	5 ms	54348 KB	Output is correct
7	Correct	7 ms	54348 KB	Output is correct
8	Correct	6 ms	54348 KB	Output is correct
9	Correct	50 ms	54348 KB	Output is correct
10	Correct	3 ms	54348 KB	Output is correct
11	Correct	1 ms	54348 KB	Output is correct
12	Correct	83 ms	54348 KB	Output is correct
13	Correct	2 ms	54348 KB	Output is correct
14	Correct	0 ms	54348 KB	Output is correct
15	Correct	1666 ms	54348 KB	Output is correct
16	Execution timed out	20000 ms	0 KB	Program timed out
17	Halted	0 ms	0 KB	-

답안 #2471

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 0.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
0.0 / 24.0