oj.uz

Submission #2484

# Submission time Handle Problem Language Result Execution time Memory
2484 2013-07-22T12:43:48 Z kriii Wombats (IOI13_wombats) C++
76 / 100
 20000 ms 36672 KB 
#include "wombats.h"
#define group_size 80

const int NON = 0x0fffffff;
const int Z = 64;
int N, M, G, Start[Z], End[Z];

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

	make();
}

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

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

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

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36672 KB Output is correct
2 Correct 0 ms 36672 KB Output is correct
3 Correct 0 ms 36672 KB Output is correct
4 Correct 2 ms 36672 KB Output is correct
5 Correct 1 ms 36672 KB Output is correct
6 Correct 1 ms 36672 KB Output is correct
7 Correct 1 ms 36672 KB Output is correct
8 Correct 1 ms 36672 KB Output is correct
9 Correct 2 ms 36672 KB Output is correct
10 Correct 2 ms 36672 KB Output is correct
11 Correct 79 ms 36672 KB Output is correct
12 Correct 2 ms 36672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 36672 KB Output is correct
2 Correct 1330 ms 36672 KB Output is correct
3 Correct 1121 ms 36672 KB Output is correct
4 Correct 1119 ms 36672 KB Output is correct
5 Correct 1250 ms 36672 KB Output is correct
6 Correct 0 ms 36672 KB Output is correct
7 Correct 0 ms 36672 KB Output is correct
8 Correct 0 ms 36672 KB Output is correct
9 Correct 7213 ms 36672 KB Output is correct
10 Correct 0 ms 36672 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36672 KB Output is correct
2 Correct 5 ms 36672 KB Output is correct
3 Correct 6 ms 36672 KB Output is correct
4 Correct 57 ms 36672 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 36672 KB Output is correct
2 Correct 1462 ms 36672 KB Output is correct
3 Correct 1320 ms 36672 KB Output is correct
4 Correct 1304 ms 36672 KB Output is correct
5 Correct 1245 ms 36672 KB Output is correct
6 Correct 2 ms 36672 KB Output is correct
7 Correct 6 ms 36672 KB Output is correct
8 Correct 7 ms 36672 KB Output is correct
9 Correct 53 ms 36672 KB Output is correct
10 Correct 2 ms 36672 KB Output is correct
11 Correct 3 ms 36672 KB Output is correct
12 Correct 105 ms 36672 KB Output is correct
13 Correct 2 ms 36672 KB Output is correct
14 Correct 0 ms 36672 KB Output is correct
15 Correct 0 ms 36672 KB Output is correct
16 Correct 0 ms 36672 KB Output is correct
17 Correct 0 ms 36672 KB Output is correct
18 Correct 2 ms 36672 KB Output is correct
19 Correct 2 ms 36672 KB Output is correct
20 Correct 2 ms 36672 KB Output is correct
21 Correct 3 ms 36672 KB Output is correct
22 Correct 2 ms 36672 KB Output is correct
23 Correct 2 ms 36672 KB Output is correct
24 Correct 1 ms 36672 KB Output is correct
25 Correct 80 ms 36672 KB Output is correct
26 Correct 1 ms 36672 KB Output is correct
27 Correct 7259 ms 36672 KB Output is correct
28 Correct 6949 ms 36672 KB Output is correct
29 Correct 8155 ms 36672 KB Output is correct
30 Correct 8044 ms 36672 KB Output is correct
31 Correct 6960 ms 36672 KB Output is correct
32 Correct 0 ms 36672 KB Output is correct

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 36672 KB Output is correct
2 Correct 1481 ms 36672 KB Output is correct
3 Correct 1335 ms 36672 KB Output is correct
4 Correct 1101 ms 36672 KB Output is correct
5 Correct 1242 ms 36672 KB Output is correct
6 Correct 5 ms 36672 KB Output is correct
7 Correct 7 ms 36672 KB Output is correct
8 Correct 6 ms 36672 KB Output is correct
9 Correct 57 ms 36672 KB Output is correct
10 Correct 0 ms 36672 KB Output is correct
11 Correct 1 ms 36672 KB Output is correct
12 Correct 77 ms 36672 KB Output is correct
13 Correct 2 ms 36672 KB Output is correct
14 Correct 1 ms 36672 KB Output is correct
15 Correct 3984 ms 36672 KB Output is correct
16 Execution timed out 20000 ms 0 KB Program timed out
17 Halted 0 ms 0 KB -