oj.uz

Submission #2493

# Submission time Handle Problem Language Result Execution time Memory
2493 2013-07-22T13:33:19 Z kriii Wombats (IOI13_wombats) C++
76 / 100
 3323 ms 176676 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -