답안 #2486 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2486	2013-07-22T12:51:32 Z	kriii	웜뱃 (IOI13_wombats)	C++	100 / 100	12266 ms	176676 KB

wombats

#include "wombats.h"
#define group_size 10

const int NON = 0x0fffffff;
const int Z = 512;
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	2 ms	176676 KB	Output is correct
2	Correct	2 ms	176676 KB	Output is correct
3	Correct	83 ms	176676 KB	Output is correct
4	Correct	2 ms	176676 KB	Output is correct
5	Correct	0 ms	176676 KB	Output is correct
6	Correct	2 ms	176676 KB	Output is correct
7	Correct	0 ms	176676 KB	Output is correct
8	Correct	0 ms	176676 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	176676 KB	Output is correct
2	Correct	0 ms	176676 KB	Output is correct
3	Correct	0 ms	176676 KB	Output is correct
4	Correct	23 ms	176676 KB	Output is correct
5	Correct	23 ms	176676 KB	Output is correct
6	Correct	23 ms	176676 KB	Output is correct
7	Correct	31 ms	176676 KB	Output is correct
8	Correct	19 ms	176676 KB	Output is correct
9	Correct	28 ms	176676 KB	Output is correct
10	Correct	25 ms	176676 KB	Output is correct
11	Correct	122 ms	176676 KB	Output is correct
12	Correct	23 ms	176676 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	847 ms	176676 KB	Output is correct
2	Correct	783 ms	176676 KB	Output is correct
3	Correct	820 ms	176676 KB	Output is correct
4	Correct	825 ms	176676 KB	Output is correct
5	Correct	808 ms	176676 KB	Output is correct
6	Correct	0 ms	176676 KB	Output is correct
7	Correct	0 ms	176676 KB	Output is correct
8	Correct	0 ms	176676 KB	Output is correct
9	Correct	2000 ms	176676 KB	Output is correct
10	Correct	0 ms	176676 KB	Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	921 ms	176676 KB	Output is correct
2	Correct	788 ms	176676 KB	Output is correct
3	Correct	970 ms	176676 KB	Output is correct
4	Correct	827 ms	176676 KB	Output is correct
5	Correct	976 ms	176676 KB	Output is correct
6	Correct	5 ms	176676 KB	Output is correct
7	Correct	7 ms	176676 KB	Output is correct
8	Correct	7 ms	176676 KB	Output is correct
9	Correct	60 ms	176676 KB	Output is correct
10	Correct	2 ms	176676 KB	Output is correct
11	Correct	3 ms	176676 KB	Output is correct
12	Correct	102 ms	176676 KB	Output is correct
13	Correct	0 ms	176676 KB	Output is correct
14	Correct	0 ms	176676 KB	Output is correct
15	Correct	1 ms	176676 KB	Output is correct
16	Correct	1 ms	176676 KB	Output is correct
17	Correct	0 ms	176676 KB	Output is correct
18	Correct	31 ms	176676 KB	Output is correct
19	Correct	18 ms	176676 KB	Output is correct
20	Correct	31 ms	176676 KB	Output is correct
21	Correct	23 ms	176676 KB	Output is correct
22	Correct	27 ms	176676 KB	Output is correct
23	Correct	22 ms	176676 KB	Output is correct
24	Correct	27 ms	176676 KB	Output is correct
25	Correct	103 ms	176676 KB	Output is correct
26	Correct	28 ms	176676 KB	Output is correct
27	Correct	2127 ms	176676 KB	Output is correct
28	Correct	2934 ms	176676 KB	Output is correct
29	Correct	3191 ms	176676 KB	Output is correct
30	Correct	2732 ms	176676 KB	Output is correct
31	Correct	2780 ms	176676 KB	Output is correct
32	Correct	1 ms	176676 KB	Output is correct

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	804 ms	176676 KB	Output is correct
2	Correct	784 ms	176676 KB	Output is correct
3	Correct	833 ms	176676 KB	Output is correct
4	Correct	837 ms	176676 KB	Output is correct
5	Correct	814 ms	176676 KB	Output is correct
6	Correct	3 ms	176676 KB	Output is correct
7	Correct	4 ms	176676 KB	Output is correct
8	Correct	6 ms	176676 KB	Output is correct
9	Correct	54 ms	176676 KB	Output is correct
10	Correct	2 ms	176676 KB	Output is correct
11	Correct	2 ms	176676 KB	Output is correct
12	Correct	86 ms	176676 KB	Output is correct
13	Correct	3 ms	176676 KB	Output is correct
14	Correct	0 ms	176676 KB	Output is correct
15	Correct	5199 ms	176676 KB	Output is correct
16	Correct	10728 ms	176676 KB	Output is correct
17	Correct	1 ms	176676 KB	Output is correct
18	Correct	0 ms	176676 KB	Output is correct
19	Correct	0 ms	176676 KB	Output is correct
20	Correct	30 ms	176676 KB	Output is correct
21	Correct	29 ms	176676 KB	Output is correct
22	Correct	22 ms	176676 KB	Output is correct
23	Correct	22 ms	176676 KB	Output is correct
24	Correct	21 ms	176676 KB	Output is correct
25	Correct	26 ms	176676 KB	Output is correct
26	Correct	22 ms	176676 KB	Output is correct
27	Correct	112 ms	176676 KB	Output is correct
28	Correct	32 ms	176676 KB	Output is correct
29	Correct	2103 ms	176676 KB	Output is correct
30	Correct	3186 ms	176676 KB	Output is correct
31	Correct	12266 ms	176676 KB	Output is correct
32	Correct	11531 ms	176676 KB	Output is correct
33	Correct	3245 ms	176676 KB	Output is correct
34	Correct	11184 ms	176676 KB	Output is correct
35	Correct	2735 ms	176676 KB	Output is correct
36	Correct	11235 ms	176676 KB	Output is correct
37	Correct	2993 ms	176676 KB	Output is correct
38	Correct	11292 ms	176676 KB	Output is correct
39	Correct	0 ms	176676 KB	Output is correct
40	Correct	11456 ms	176676 KB	Output is correct

답안 #2486

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 24.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
24.0 / 24.0