oj.uz

Submission #280168

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

void MakeAll(){
	memset(dp, 63, sizeof dp);
	for (int i = 0; i < C; i++)
		dp[0][i][i] = 0;
	for (int i = 0; i < R; i += T){
		for (int j = 0; j < C; j++)
			for (int k = 0; k < C; k++)
				for (int x = 0; x < C; x++)
					dp[1][j][k] = min(dp[1][j][k], dp[0][j][x] + bl[i/T][x][k]);
		for (int j = 0; j < C; j++)
			for (int k = 0; k < C; k++)
				dp[0][j][k] = dp[1][j][k], dp[1][j][k] = inf;
	}
}

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 15 ms 12416 KB Output is correct
2 Correct 15 ms 12416 KB Output is correct
3 Correct 100 ms 15224 KB Output is correct
4 Correct 20 ms 12416 KB Output is correct
5 Correct 16 ms 12416 KB Output is correct
6 Correct 8 ms 8448 KB Output is correct
7 Correct 7 ms 8448 KB Output is correct
8 Correct 7 ms 8448 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8448 KB Output is correct
2 Correct 6 ms 8448 KB Output is correct
3 Correct 7 ms 8448 KB Output is correct
4 Correct 7 ms 8576 KB Output is correct
5 Correct 7 ms 8576 KB Output is correct
6 Correct 7 ms 8576 KB Output is correct
7 Correct 7 ms 8576 KB Output is correct
8 Correct 7 ms 8576 KB Output is correct
9 Correct 9 ms 8576 KB Output is correct
10 Correct 7 ms 8480 KB Output is correct
11 Correct 103 ms 10976 KB Output is correct
12 Correct 8 ms 8576 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 8840 KB Output is correct
2 Correct 1006 ms 8832 KB Output is correct
3 Correct 1061 ms 8848 KB Output is correct
4 Correct 1077 ms 8968 KB Output is correct
5 Correct 1035 ms 8844 KB Output is correct
6 Correct 9 ms 8448 KB Output is correct
7 Correct 8 ms 8448 KB Output is correct
8 Correct 6 ms 8448 KB Output is correct
9 Correct 5232 ms 8952 KB Output is correct
10 Correct 7 ms 8448 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16384 KB Output is correct
2 Correct 31 ms 16384 KB Output is correct
3 Correct 27 ms 16384 KB Output is correct
4 Correct 69 ms 17756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 8924 KB Output is correct
2 Correct 1073 ms 8828 KB Output is correct
3 Correct 1109 ms 8832 KB Output is correct
4 Correct 1077 ms 8852 KB Output is correct
5 Correct 1050 ms 8848 KB Output is correct
6 Correct 27 ms 16384 KB Output is correct
7 Correct 31 ms 16384 KB Output is correct
8 Correct 33 ms 16448 KB Output is correct
9 Correct 79 ms 17784 KB Output is correct
10 Correct 16 ms 12416 KB Output is correct
11 Correct 15 ms 12416 KB Output is correct
12 Correct 141 ms 15172 KB Output is correct
13 Correct 15 ms 12416 KB Output is correct
14 Correct 16 ms 12416 KB Output is correct
15 Correct 6 ms 8448 KB Output is correct
16 Correct 8 ms 8552 KB Output is correct
17 Correct 8 ms 8448 KB Output is correct
18 Correct 9 ms 8576 KB Output is correct
19 Correct 9 ms 8576 KB Output is correct
20 Correct 9 ms 8576 KB Output is correct
21 Correct 7 ms 8576 KB Output is correct
22 Correct 10 ms 8576 KB Output is correct
23 Correct 7 ms 8576 KB Output is correct
24 Correct 8 ms 8552 KB Output is correct
25 Correct 107 ms 10916 KB Output is correct
26 Correct 9 ms 8576 KB Output is correct
27 Correct 5381 ms 8844 KB Output is correct
28 Execution timed out 20095 ms 20940 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1026 ms 8832 KB Output is correct
2 Correct 1010 ms 8832 KB Output is correct
3 Correct 1050 ms 8848 KB Output is correct
4 Correct 1044 ms 8848 KB Output is correct
5 Correct 1020 ms 8848 KB Output is correct
6 Correct 29 ms 16384 KB Output is correct
7 Correct 26 ms 16384 KB Output is correct
8 Correct 30 ms 16384 KB Output is correct
9 Correct 68 ms 17784 KB Output is correct
10 Correct 15 ms 12416 KB Output is correct
11 Correct 16 ms 12416 KB Output is correct
12 Correct 106 ms 15352 KB Output is correct
13 Correct 16 ms 12416 KB Output is correct
14 Correct 15 ms 12416 KB Output is correct
15 Correct 3386 ms 27252 KB Output is correct
16 Execution timed out 20070 ms 25680 KB Time limit exceeded
17 Halted 0 ms 0 KB -