답안 #2493 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2493	2013-07-22T13:33:19 Z	kriii	웜뱃 (IOI13_wombats)	C++	76 / 100	3323 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],NOW[200];
int H[5001][200],V[5001][200];

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

void merge(int x)
{
	int i,j,k,s,p;

	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;
	}
}

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

	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++){
				for (j=1;j<M;j++) NOW[j] = min(NOW[j],NOW[j-1]+H[k][j-1]);
				for (j=M-2;j>=0;j--) NOW[j] = min(NOW[j],NOW[j+1]+H[k][j]);
				for (j=0;j<M;j++) NOW[j] += V[k][j];
			}
			for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
		}
	}
}

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,c;
	for (i=c=0;i<G;i++){
		Start[i] = c;
		c += group_size;
		End[i] = c;
	}
	if (End[G-1] >= R) End[G-1] = R;
	if (Start[G-1] == End[G-1]) G--;

	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];
	for (i=0;i<Z;i++) modify(i);
	for (i=Z-1;i>=1;i--) merge(i);
}

void change(int g)
{
	modify(g);
	int x = (g + Z) / 2;
	while (x){
		merge(x);
		x >>= 1;
	}
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	change(P/group_size);
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	change(P/group_size);
}

int escape(int V1, int V2) {
	return GO[1][V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	176676 KB	Output is correct
2	Correct	0 ms	176676 KB	Output is correct
3	Correct	86 ms	176676 KB	Output is correct
4	Correct	3 ms	176676 KB	Output is correct
5	Correct	1 ms	176676 KB	Output is correct
6	Correct	0 ms	176676 KB	Output is correct
7	Correct	1 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	0 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	3 ms	176676 KB	Output is correct
5	Correct	5 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	5 ms	176676 KB	Output is correct
10	Correct	9 ms	176676 KB	Output is correct
11	Correct	103 ms	176676 KB	Output is correct
12	Correct	3 ms	176676 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	330 ms	176676 KB	Output is correct
2	Correct	364 ms	176676 KB	Output is correct
3	Correct	389 ms	176676 KB	Output is correct
4	Correct	396 ms	176676 KB	Output is correct
5	Correct	388 ms	176676 KB	Output is correct
6	Correct	0 ms	176676 KB	Output is correct
7	Correct	1 ms	176676 KB	Output is correct
8	Correct	0 ms	176676 KB	Output is correct
9	Correct	1374 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	3 ms	176676 KB	Output is correct
2	Correct	4 ms	176676 KB	Output is correct
3	Correct	4 ms	176676 KB	Output is correct
4	Correct	48 ms	176676 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	325 ms	176676 KB	Output is correct
2	Correct	306 ms	176676 KB	Output is correct
3	Correct	400 ms	176676 KB	Output is correct
4	Correct	322 ms	176676 KB	Output is correct
5	Correct	316 ms	176676 KB	Output is correct
6	Correct	4 ms	176676 KB	Output is correct
7	Correct	2 ms	176676 KB	Output is correct
8	Correct	3 ms	176676 KB	Output is correct
9	Correct	48 ms	176676 KB	Output is correct
10	Correct	4 ms	176676 KB	Output is correct
11	Correct	2 ms	176676 KB	Output is correct
12	Correct	101 ms	176676 KB	Output is correct
13	Correct	1 ms	176676 KB	Output is correct
14	Correct	1 ms	176676 KB	Output is correct
15	Correct	0 ms	176676 KB	Output is correct
16	Correct	0 ms	176676 KB	Output is correct
17	Correct	0 ms	176676 KB	Output is correct
18	Correct	3 ms	176676 KB	Output is correct
19	Correct	3 ms	176676 KB	Output is correct
20	Correct	3 ms	176676 KB	Output is correct
21	Correct	6 ms	176676 KB	Output is correct
22	Correct	4 ms	176676 KB	Output is correct
23	Correct	4 ms	176676 KB	Output is correct
24	Correct	1 ms	176676 KB	Output is correct
25	Correct	81 ms	176676 KB	Output is correct
26	Correct	3 ms	176676 KB	Output is correct
27	Correct	1168 ms	176676 KB	Output is correct
28	Correct	1846 ms	176676 KB	Output is correct
29	Correct	1810 ms	176676 KB	Output is correct
30	Correct	2084 ms	176676 KB	Output is correct
31	Correct	1909 ms	176676 KB	Output is correct
32	Correct	0 ms	176676 KB	Output is correct

Subtask #6
0.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	316 ms	176676 KB	Output is correct
2	Correct	308 ms	176676 KB	Output is correct
3	Correct	327 ms	176676 KB	Output is correct
4	Correct	383 ms	176676 KB	Output is correct
5	Correct	327 ms	176676 KB	Output is correct
6	Correct	2 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	57 ms	176676 KB	Output is correct
10	Correct	2 ms	176676 KB	Output is correct
11	Correct	1 ms	176676 KB	Output is correct
12	Correct	97 ms	176676 KB	Output is correct
13	Correct	2 ms	176676 KB	Output is correct
14	Correct	2 ms	176676 KB	Output is correct
15	Incorrect	3323 ms	176676 KB	Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
16	Halted	0 ms	0 KB	-

답안 #2493

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