oj.uz

Submission #2470

# Submission time Handle Problem Language Result Execution time Memory
2470 2013-07-22T07:49:45 Z ainta Wombats (IOI13_wombats) C++
0 / 100
 248 ms 101684 KB 
#include "wombats.h"
#define SZ 256
#define INF 999999999
int D[512][201][201],bucket_sz,h[5010][210],v[5010][210],TP[23][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,b,e,w[201],s,l;
	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++)w[i]=0;
	w[0]=c-1;
	for(i=c-2;i>-c;i--){
		b=-i;e=c-1-i;
		if(b<0)b=0;
		if(e>=c)e=c-1;
		for(j=b;j<=e;j++){
			if(j==b)s=0;
			else s=w[j-1];
			if(j==e)l=c-1;
			else l=w[j];
			for(k=s;k<=l;k++){
				if(D[a][j][j+i]>D[c1][j][k]+D[c2][k][j+i]){
					D[a][j][j+i]=D[c1][j][k]+D[c2][k][j+i];
					w[j]=k;
				}
			}
		}
	}
}
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)/256+1;
	for(i=0;i<R;i+=bucket_sz)
	{
		Do(SZ+i/bucket_sz,i);
	}
	for(i=SZ+i/bucket_sz;i<512;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
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 101684 KB Output is correct
2 Correct 172 ms 101684 KB Output is correct
3 Correct 220 ms 101684 KB Output is correct
4 Correct 218 ms 101684 KB Output is correct
5 Correct 209 ms 101684 KB Output is correct
6 Incorrect 0 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 101684 KB Output is correct
2 Correct 172 ms 101684 KB Output is correct
3 Correct 213 ms 101684 KB Output is correct
4 Correct 213 ms 101684 KB Output is correct
5 Correct 204 ms 101684 KB Output is correct
6 Incorrect 1 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 101684 KB Output is correct
2 Correct 165 ms 101684 KB Output is correct
3 Correct 214 ms 101684 KB Output is correct
4 Correct 212 ms 101684 KB Output is correct
5 Correct 206 ms 101684 KB Output is correct
6 Incorrect 3 ms 101684 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
7 Halted 0 ms 0 KB -