Submission #2490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2490	2013-07-22T13:18:25 Z	kriii	Wombats (IOI13_wombats)	C++	100 / 100	11590 ms	176680 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 H[5001][200],V[5001][200];

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

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

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

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

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

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	176680 KB	Output is correct
2	Correct	2 ms	176680 KB	Output is correct
3	Correct	90 ms	176680 KB	Output is correct
4	Correct	2 ms	176680 KB	Output is correct
5	Correct	0 ms	176680 KB	Output is correct
6	Correct	0 ms	176680 KB	Output is correct
7	Correct	0 ms	176680 KB	Output is correct
8	Correct	0 ms	176680 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	176680 KB	Output is correct
2	Correct	1 ms	176680 KB	Output is correct
3	Correct	0 ms	176680 KB	Output is correct
4	Correct	22 ms	176680 KB	Output is correct
5	Correct	31 ms	176680 KB	Output is correct
6	Correct	26 ms	176680 KB	Output is correct
7	Correct	30 ms	176680 KB	Output is correct
8	Correct	25 ms	176680 KB	Output is correct
9	Correct	23 ms	176680 KB	Output is correct
10	Correct	21 ms	176680 KB	Output is correct
11	Correct	100 ms	176680 KB	Output is correct
12	Correct	23 ms	176680 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1011 ms	176680 KB	Output is correct
2	Correct	894 ms	176680 KB	Output is correct
3	Correct	816 ms	176680 KB	Output is correct
4	Correct	822 ms	176680 KB	Output is correct
5	Correct	994 ms	176680 KB	Output is correct
6	Correct	1 ms	176680 KB	Output is correct
7	Correct	0 ms	176680 KB	Output is correct
8	Correct	0 ms	176680 KB	Output is correct
9	Correct	2131 ms	176680 KB	Output is correct
10	Correct	1 ms	176680 KB	Output is correct

Subtask #4
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	176680 KB	Output is correct
2	Correct	2 ms	176680 KB	Output is correct
3	Correct	7 ms	176680 KB	Output is correct
4	Correct	42 ms	176680 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	959 ms	176680 KB	Output is correct
2	Correct	963 ms	176680 KB	Output is correct
3	Correct	1004 ms	176680 KB	Output is correct
4	Correct	980 ms	176680 KB	Output is correct
5	Correct	808 ms	176680 KB	Output is correct
6	Correct	6 ms	176680 KB	Output is correct
7	Correct	7 ms	176680 KB	Output is correct
8	Correct	5 ms	176680 KB	Output is correct
9	Correct	63 ms	176680 KB	Output is correct
10	Correct	3 ms	176680 KB	Output is correct
11	Correct	2 ms	176680 KB	Output is correct
12	Correct	101 ms	176680 KB	Output is correct
13	Correct	1 ms	176680 KB	Output is correct
14	Correct	1 ms	176680 KB	Output is correct
15	Correct	0 ms	176680 KB	Output is correct
16	Correct	0 ms	176680 KB	Output is correct
17	Correct	0 ms	176680 KB	Output is correct
18	Correct	22 ms	176680 KB	Output is correct
19	Correct	24 ms	176680 KB	Output is correct
20	Correct	28 ms	176680 KB	Output is correct
21	Correct	28 ms	176680 KB	Output is correct
22	Correct	19 ms	176680 KB	Output is correct
23	Correct	29 ms	176680 KB	Output is correct
24	Correct	31 ms	176680 KB	Output is correct
25	Correct	102 ms	176680 KB	Output is correct
26	Correct	29 ms	176680 KB	Output is correct
27	Correct	1791 ms	176680 KB	Output is correct
28	Correct	3068 ms	176680 KB	Output is correct
29	Correct	3023 ms	176680 KB	Output is correct
30	Correct	2643 ms	176680 KB	Output is correct
31	Correct	2888 ms	176680 KB	Output is correct
32	Correct	2 ms	176680 KB	Output is correct

Subtask #6
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	846 ms	176680 KB	Output is correct
2	Correct	785 ms	176680 KB	Output is correct
3	Correct	1028 ms	176680 KB	Output is correct
4	Correct	988 ms	176680 KB	Output is correct
5	Correct	829 ms	176680 KB	Output is correct
6	Correct	3 ms	176680 KB	Output is correct
7	Correct	5 ms	176680 KB	Output is correct
8	Correct	8 ms	176680 KB	Output is correct
9	Correct	52 ms	176680 KB	Output is correct
10	Correct	2 ms	176680 KB	Output is correct
11	Correct	1 ms	176680 KB	Output is correct
12	Correct	90 ms	176680 KB	Output is correct
13	Correct	1 ms	176680 KB	Output is correct
14	Correct	3 ms	176680 KB	Output is correct
15	Correct	5957 ms	176680 KB	Output is correct
16	Correct	10648 ms	176680 KB	Output is correct
17	Correct	0 ms	176680 KB	Output is correct
18	Correct	0 ms	176680 KB	Output is correct
19	Correct	0 ms	176680 KB	Output is correct
20	Correct	21 ms	176680 KB	Output is correct
21	Correct	22 ms	176680 KB	Output is correct
22	Correct	26 ms	176680 KB	Output is correct
23	Correct	23 ms	176680 KB	Output is correct
24	Correct	19 ms	176680 KB	Output is correct
25	Correct	29 ms	176680 KB	Output is correct
26	Correct	20 ms	176680 KB	Output is correct
27	Correct	107 ms	176680 KB	Output is correct
28	Correct	23 ms	176680 KB	Output is correct
29	Correct	2040 ms	176680 KB	Output is correct
30	Correct	2997 ms	176680 KB	Output is correct
31	Correct	11590 ms	176680 KB	Output is correct
32	Correct	10203 ms	176680 KB	Output is correct
33	Correct	2600 ms	176680 KB	Output is correct
34	Correct	10090 ms	176680 KB	Output is correct
35	Correct	2640 ms	176680 KB	Output is correct
36	Correct	10163 ms	176680 KB	Output is correct
37	Correct	3149 ms	176680 KB	Output is correct
38	Correct	10231 ms	176680 KB	Output is correct
39	Correct	0 ms	176680 KB	Output is correct
40	Correct	10318 ms	176680 KB	Output is correct

Submission #2490

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