oj.uz

Submission #280194

# Submission time Handle Problem Language Result Execution time Memory
280194 2020-08-22T14:49:05 Z Saboon Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 23964 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 230;
int R, C, H[5000][200], V[5000][200];
int bl[30][200][200], dp[2][200][200];

void calc(int l, int r, int lo, int hi, int block, int V1){
	if (l >= r)
		return;
	int m = (l+r) >> 1, opt = -1;
	dp[1][V1][m] = inf;
	for (int i = lo; i < hi; i++){
		if (dp[0][V1][i] + bl[block][i][m] < dp[1][V1][m]){
			opt = i;
			dp[1][V1][m] = dp[0][V1][i] + bl[block][i][m];
		}
	}
	calc(l, m, lo, opt+1, block, V1);
	calc(m+1, r, opt, hi, block, V1);
}

void MakeAll(){
	for (int V1 = 0; V1 < C; V1++){
		for (int i = 0; i < C; i++)
			dp[0][V1][i] = bl[0][V1][i];
		for (int i = T; i < R; i += T){
			int block = i/T;
			calc(0, C, 0, C, block, V1);
			for (int j = 0; j < C; j++)
				dp[0][V1][j] = dp[1][V1][j];
		}
	}
}

void ChangeBlock(int block){
	for (int j = 0; j < C; j++){
		for (int k = 0; k < C; k++)
			bl[block][j][k] = inf;
		bl[block][j][j] = 0;
		for (int k = j+1; k < C; k++)
			bl[block][j][k] = bl[block][j][k-1] + H[T*block][k-1];
		for (int k = j-1; k >= 0; k--)
			bl[block][j][k] = bl[block][j][k+1] + H[T*block][k];
		for (int k = 0; k < C; k++)
			bl[block][j][k] += V[T*block][k];
		for (int i = T*block+1; i < min(R, T*(block+1)); i++){
			for (int k = 1; k < C; k++)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k-1] + H[i][k-1]);
			for (int k = C-2; k >= 0; k--)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k+1] + H[i][k]);
			for (int k = 0; k < C; k++)
				bl[block][j][k] += V[i][k];
		}
	}
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	R = r, C = c;
	for (int i = 0; i < 5000; i++)
		for (int j = 0; j < 200; j++)
			H[i][j] = h[i][j], V[i][j] = v[i][j];
	for (int i = 0; i < R; i += T)
		ChangeBlock(i/T);
	MakeAll();
	return;
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	ChangeBlock(P/T);
	MakeAll();
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	ChangeBlock(P/T);
	MakeAll();
}

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

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 93 ms 14968 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 7 ms 8192 KB Output is correct
7 Correct 7 ms 8192 KB Output is correct
8 Correct 7 ms 8192 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 7 ms 8192 KB Output is correct
3 Correct 7 ms 8192 KB Output is correct
4 Correct 7 ms 8192 KB Output is correct
5 Correct 7 ms 8192 KB Output is correct
6 Correct 7 ms 8188 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 7 ms 8192 KB Output is correct
9 Correct 7 ms 8192 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct
11 Correct 99 ms 10620 KB Output is correct
12 Correct 7 ms 8180 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 8696 KB Output is correct
2 Correct 888 ms 8572 KB Output is correct
3 Correct 913 ms 8568 KB Output is correct
4 Correct 907 ms 8576 KB Output is correct
5 Correct 924 ms 8616 KB Output is correct
6 Correct 8 ms 8192 KB Output is correct
7 Correct 7 ms 8192 KB Output is correct
8 Correct 7 ms 8192 KB Output is correct
9 Correct 4500 ms 8612 KB Output is correct
10 Correct 6 ms 8192 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 17 ms 16128 KB Output is correct
4 Correct 58 ms 17532 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 8576 KB Output is correct
2 Correct 881 ms 8696 KB Output is correct
3 Correct 917 ms 8616 KB Output is correct
4 Correct 907 ms 8620 KB Output is correct
5 Correct 886 ms 8576 KB Output is correct
6 Correct 15 ms 16128 KB Output is correct
7 Correct 14 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 58 ms 17572 KB Output is correct
10 Correct 10 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 91 ms 14968 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 7 ms 8192 KB Output is correct
16 Correct 7 ms 8192 KB Output is correct
17 Correct 6 ms 8192 KB Output is correct
18 Correct 7 ms 8192 KB Output is correct
19 Correct 6 ms 8192 KB Output is correct
20 Correct 7 ms 8192 KB Output is correct
21 Correct 7 ms 8192 KB Output is correct
22 Correct 7 ms 8192 KB Output is correct
23 Correct 7 ms 8192 KB Output is correct
24 Correct 7 ms 8192 KB Output is correct
25 Correct 109 ms 10744 KB Output is correct
26 Correct 8 ms 8192 KB Output is correct
27 Correct 4530 ms 8608 KB Output is correct
28 Correct 13298 ms 22316 KB Output is correct
29 Correct 13368 ms 20364 KB Output is correct
30 Correct 13345 ms 20116 KB Output is correct
31 Correct 14407 ms 23964 KB Output is correct
32 Correct 6 ms 8192 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 8612 KB Output is correct
2 Correct 907 ms 8600 KB Output is correct
3 Correct 911 ms 8612 KB Output is correct
4 Correct 909 ms 8576 KB Output is correct
5 Correct 888 ms 8576 KB Output is correct
6 Correct 15 ms 16128 KB Output is correct
7 Correct 15 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 58 ms 17528 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 12 ms 12160 KB Output is correct
12 Correct 95 ms 14968 KB Output is correct
13 Correct 9 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 2526 ms 21956 KB Output is correct
16 Execution timed out 20048 ms 22212 KB Time limit exceeded
17 Halted 0 ms 0 KB -