oj.uz

Submission #280377

# Submission time Handle Problem Language Result Execution time Memory
280377 2020-08-22T17:01:36 Z Saboon Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 59512 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 20;
int R, C, H[5000][200], V[5000][200];
int bl[255][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 12 ms 13184 KB Output is correct
2 Correct 12 ms 13184 KB Output is correct
3 Correct 99 ms 15992 KB Output is correct
4 Correct 12 ms 13184 KB Output is correct
5 Correct 12 ms 13184 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 8 ms 8192 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
9 Correct 7 ms 8192 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct
11 Correct 94 ms 10744 KB Output is correct
12 Correct 7 ms 8192 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 9012 KB Output is correct
2 Correct 292 ms 8952 KB Output is correct
3 Correct 324 ms 8960 KB Output is correct
4 Correct 324 ms 8960 KB Output is correct
5 Correct 319 ms 9088 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
9 Correct 1383 ms 9016 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17280 KB Output is correct
2 Correct 23 ms 17280 KB Output is correct
3 Correct 23 ms 17280 KB Output is correct
4 Correct 65 ms 18680 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 8936 KB Output is correct
2 Correct 276 ms 8960 KB Output is correct
3 Correct 327 ms 8960 KB Output is correct
4 Correct 322 ms 8960 KB Output is correct
5 Correct 316 ms 9088 KB Output is correct
6 Correct 23 ms 17280 KB Output is correct
7 Correct 22 ms 17280 KB Output is correct
8 Correct 24 ms 17280 KB Output is correct
9 Correct 66 ms 18680 KB Output is correct
10 Correct 12 ms 13184 KB Output is correct
11 Correct 12 ms 13184 KB Output is correct
12 Correct 95 ms 15992 KB Output is correct
13 Correct 12 ms 13184 KB Output is correct
14 Correct 12 ms 13184 KB Output is correct
15 Correct 7 ms 8192 KB Output is correct
16 Correct 7 ms 8192 KB Output is correct
17 Correct 7 ms 8192 KB Output is correct
18 Correct 7 ms 8192 KB Output is correct
19 Correct 7 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 8320 KB Output is correct
24 Correct 7 ms 8192 KB Output is correct
25 Correct 94 ms 10744 KB Output is correct
26 Correct 7 ms 8192 KB Output is correct
27 Correct 1367 ms 9012 KB Output is correct
28 Execution timed out 20089 ms 38520 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 9080 KB Output is correct
2 Correct 281 ms 8960 KB Output is correct
3 Correct 325 ms 9080 KB Output is correct
4 Correct 323 ms 9080 KB Output is correct
5 Correct 320 ms 9080 KB Output is correct
6 Correct 23 ms 17280 KB Output is correct
7 Correct 22 ms 17280 KB Output is correct
8 Correct 23 ms 17280 KB Output is correct
9 Correct 67 ms 18680 KB Output is correct
10 Correct 14 ms 13184 KB Output is correct
11 Correct 12 ms 13184 KB Output is correct
12 Correct 97 ms 15896 KB Output is correct
13 Correct 12 ms 13184 KB Output is correct
14 Correct 12 ms 13184 KB Output is correct
15 Correct 5174 ms 59512 KB Output is correct
16 Execution timed out 20043 ms 58588 KB Time limit exceeded
17 Halted 0 ms 0 KB -