답안 #2485 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2485	2013-07-22T12:49:16 Z	kriii	웜뱃 (IOI13_wombats)	C++	76 / 100	20000 ms	56672 KB

wombats

#include "wombats.h"
#define group_size 50

const int NON = 0x0fffffff;
const int Z = 128;
int N, M, G, Start[Z], End[Z], MADE;
int ANS[200][200],GO[Z*2][200][200];
int NOW[200],LEFT[200],RIGHT[200];
int HH[5000][200],VV[5000][200];

inline int min(int a, int b){return a < b ? a : b;}

void going(int i)
{
	int j;

	for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j];
	for (j=1;j<M;j++){
		if (LEFT[j-1] == NON) continue;
		LEFT[j] = min(LEFT[j],LEFT[j-1]+HH[i][j-1]);
	}
	for (j=M-2;j>=0;j--){
		if (RIGHT[j+1] == NON) continue;
		RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+HH[i][j]);
	}
	for (j=0;j<M;j++){
		NOW[j] = min(NOW[j],LEFT[j]);
		NOW[j] = min(NOW[j],RIGHT[j]);
	}
}

void make()
{
	int i,j;

	for (i=0;i<M;i++){
		for (j=0;j<M;j++) NOW[j] = GO[1][i][j];
		going(N-1);
		for (j=0;j<M;j++) ANS[i][j] = NOW[j];
	}
}

void modify(int g)
{
	int i,j,k,x=g+Z,s,p;

	if (g >= G){
		for (i=0;i<M;i++){
			for (j=0;j<M;j++){
				GO[x][i][j] = i == j ? 0 : NON;
			}
		}
	}
	else{
		for (i=0;i<M;i++){
			for (j=0;j<M;j++) NOW[j] = NON;
			NOW[i] = 0;
			for (k=Start[g];k<End[g];k++){
				going(k);
				for (j=0;j<M;j++) NOW[j] += VV[k][j];
			}
			for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
		}
	}

	x /= 2;
	while (x){
		NOW[0] = 0; NOW[1] = M-1;
		for (i=M-1;i>=0;i--){
			for (j=M-1;j>=i;j--){
				s = NON; p = NOW[j-i];
				for (k=NOW[j-i];k<=NOW[j-i+1];k++){
					int &a = GO[x*2][j-i][k];
					int &b = GO[x*2+1][k][j];
					if (s >= a + b){
						s = a + b;
						p = k;
					}
				}
				GO[x][j-i][j] = s;
				NOW[j-i+1] = p;
			}
			NOW[M-i+1] = M-1;
		}

		NOW[0] = 0; NOW[1] = M-1;
		for (i=M-1;i>=0;i--){
			for (j=M-1;j>=i;j--){
				s = NON; p = NOW[j-i];
				for (k=NOW[j-i];k<=NOW[j-i+1];k++){
					int &a = GO[x*2][j][k];
					int &b = GO[x*2+1][k][j-i];
					if (s >= a + b){
						s = a + b;
						p = k;
					}
				}
				GO[x][j][j-i] = s;
				NOW[j-i+1] = p;
			}
			NOW[M-i+1] = M-1;
		}

		x /= 2;
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	N = R; M = C;
	G = (R + group_size - 1) / group_size; int i,j;
	for (i=0;i<G;i++){
		Start[i] = i * group_size;
		End[i] = (i + 1) * group_size;
	}
	if (End[G-1] >= R) End[G-1] = R-1;
	if (Start[G-1] == End[G-1]) G--;

	for (i=0;i<R;i++) for (j=0;j<C-1;j++) HH[i][j] = H[i][j];
	for (i=0;i<R-1;i++) for (j=0;j<C;j++) VV[i][j] = V[i][j];
	for (i=0;i<Z;i++) modify(i);

	MADE = 0;
}

void changeH(int P, int Q, int W) {
	HH[P][Q] = W;
	modify(P/group_size);
	MADE = 0;
}

void changeV(int P, int Q, int W) {
	VV[P][Q] = W;
	modify(P/group_size);
	MADE = 0;
}

int escape(int V1, int V2) {
	if (MADE == 0){
		make(); MADE = 1;
	}
	return ANS[V1][V2];
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1027 ms	56672 KB	Output is correct
2	Correct	1038 ms	56672 KB	Output is correct
3	Correct	903 ms	56672 KB	Output is correct
4	Correct	1081 ms	56672 KB	Output is correct
5	Correct	890 ms	56672 KB	Output is correct
6	Correct	0 ms	56672 KB	Output is correct
7	Correct	0 ms	56672 KB	Output is correct
8	Correct	0 ms	56672 KB	Output is correct
9	Correct	4761 ms	56672 KB	Output is correct
10	Correct	0 ms	56672 KB	Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	871 ms	56672 KB	Output is correct
2	Correct	880 ms	56672 KB	Output is correct
3	Correct	900 ms	56672 KB	Output is correct
4	Correct	1088 ms	56672 KB	Output is correct
5	Correct	892 ms	56672 KB	Output is correct
6	Correct	3 ms	56672 KB	Output is correct
7	Correct	3 ms	56672 KB	Output is correct
8	Correct	5 ms	56672 KB	Output is correct
9	Correct	43 ms	56672 KB	Output is correct
10	Correct	0 ms	56672 KB	Output is correct
11	Correct	2 ms	56672 KB	Output is correct
12	Correct	80 ms	56672 KB	Output is correct
13	Correct	2 ms	56672 KB	Output is correct
14	Correct	0 ms	56672 KB	Output is correct
15	Correct	0 ms	56672 KB	Output is correct
16	Correct	0 ms	56672 KB	Output is correct
17	Correct	0 ms	56672 KB	Output is correct
18	Correct	5 ms	56672 KB	Output is correct
19	Correct	4 ms	56672 KB	Output is correct
20	Correct	5 ms	56672 KB	Output is correct
21	Correct	6 ms	56672 KB	Output is correct
22	Correct	4 ms	56672 KB	Output is correct
23	Correct	4 ms	56672 KB	Output is correct
24	Correct	3 ms	56672 KB	Output is correct
25	Correct	101 ms	56672 KB	Output is correct
26	Correct	5 ms	56672 KB	Output is correct
27	Correct	4767 ms	56672 KB	Output is correct
28	Correct	5767 ms	56672 KB	Output is correct
29	Correct	5291 ms	56672 KB	Output is correct
30	Correct	5676 ms	56672 KB	Output is correct
31	Correct	5803 ms	56672 KB	Output is correct
32	Correct	0 ms	56672 KB	Output is correct

Subtask #6
0.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	877 ms	56672 KB	Output is correct
2	Correct	894 ms	56672 KB	Output is correct
3	Correct	1054 ms	56672 KB	Output is correct
4	Correct	1059 ms	56672 KB	Output is correct
5	Correct	896 ms	56672 KB	Output is correct
6	Correct	6 ms	56672 KB	Output is correct
7	Correct	5 ms	56672 KB	Output is correct
8	Correct	4 ms	56672 KB	Output is correct
9	Correct	44 ms	56672 KB	Output is correct
10	Correct	2 ms	56672 KB	Output is correct
11	Correct	1 ms	56672 KB	Output is correct
12	Correct	82 ms	56672 KB	Output is correct
13	Correct	2 ms	56672 KB	Output is correct
14	Correct	4 ms	56672 KB	Output is correct
15	Correct	3658 ms	56672 KB	Output is correct
16	Correct	19414 ms	56672 KB	Output is correct
17	Correct	0 ms	56672 KB	Output is correct
18	Correct	0 ms	56672 KB	Output is correct
19	Correct	0 ms	56672 KB	Output is correct
20	Correct	5 ms	56672 KB	Output is correct
21	Correct	3 ms	56672 KB	Output is correct
22	Correct	4 ms	56672 KB	Output is correct
23	Correct	3 ms	56672 KB	Output is correct
24	Correct	3 ms	56672 KB	Output is correct
25	Correct	3 ms	56672 KB	Output is correct
26	Correct	3 ms	56672 KB	Output is correct
27	Correct	79 ms	56672 KB	Output is correct
28	Correct	6 ms	56672 KB	Output is correct
29	Correct	4018 ms	56672 KB	Output is correct
30	Correct	4904 ms	56672 KB	Output is correct
31	Execution timed out	20000 ms	0 KB	Program timed out
32	Halted	0 ms	0 KB	-

답안 #2485

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