oj.uz

Submission #763407

# Submission time Handle Problem Language Result Execution time Memory
763407 2023-06-22T09:24:15 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26132 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxN = 5e3 + 20;
const int maxM = 2e2 + 20;
const int maxB = 1e3 + 20;
int hor[maxN][maxM];
int ver[maxN][maxM];
int tmp[maxN][maxM];
int dp[maxN][maxM];
int tree[maxB][maxM][maxM];
int N, M;

void calc(int id, int lt, int rt) {
	for (int X = 0; X < M; X++) {
		dp[lt][X] = 0;
		for (int i = X - 1; i >= 0; i--) {
			dp[lt][i] = dp[lt][i + 1] + hor[lt][i];
		}
		for (int i = X + 1; i < M; i++) {
			dp[lt][i] = dp[lt][i - 1] + hor[lt][i - 1];
		}
		for (int i = lt + 1; i <= rt; i++) {
			for (int j = 0; j < M; j++) {
				tmp[i][j] = dp[i - 1][j] + ver[i - 1][j];
				dp[i][j] = tmp[i][j];
			}
			int best = tmp[i][0];
			for (int j = 1; j < M; j++) {
				best = min(best + hor[i][j - 1], tmp[i][j]);
				dp[i][j] = min(dp[i][j], best);
			}
			best = tmp[i][M - 1];
			for (int j = M - 2; j >= 0; j--) {
				best = min(best + hor[i][j], tmp[i][j]);
				dp[i][j] = min(dp[i][j], best);
			}
		}
		for (int Y = 0; Y < M; Y++) {
			tree[id][X][Y] = dp[rt][Y];
		}
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	N = R;
	M = C;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			hor[i][j] = H[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			ver[i][j] = V[i][j];
		}
	}
	calc(1, 0, N - 1);
}

void changeH(int P, int Q, int W) {
	hor[P][Q] = W;
	calc(1, 0, N - 1);
}

void changeV(int P, int Q, int W) {
	ver[P][Q] = W;
	calc(1, 0, N - 1);
}

int escape(int X, int Y) {
	return tree[1][X][Y];
}

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 19 ms 17108 KB Output is correct
2 Correct 20 ms 17072 KB Output is correct
3 Correct 73 ms 18640 KB Output is correct
4 Correct 23 ms 17100 KB Output is correct
5 Correct 23 ms 17156 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 53 ms 1376 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 920 KB Output is correct
2 Correct 356 ms 980 KB Output is correct
3 Correct 369 ms 892 KB Output is correct
4 Correct 374 ms 932 KB Output is correct
5 Correct 362 ms 924 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1848 ms 944 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 25368 KB Output is correct
2 Correct 58 ms 25360 KB Output is correct
3 Correct 73 ms 25352 KB Output is correct
4 Correct 88 ms 26132 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 936 KB Output is correct
2 Correct 358 ms 920 KB Output is correct
3 Correct 372 ms 940 KB Output is correct
4 Correct 369 ms 928 KB Output is correct
5 Correct 381 ms 1004 KB Output is correct
6 Correct 55 ms 25372 KB Output is correct
7 Correct 58 ms 25356 KB Output is correct
8 Correct 59 ms 25300 KB Output is correct
9 Correct 88 ms 26080 KB Output is correct
10 Correct 20 ms 17160 KB Output is correct
11 Correct 24 ms 17160 KB Output is correct
12 Correct 84 ms 18876 KB Output is correct
13 Correct 24 ms 17108 KB Output is correct
14 Correct 22 ms 17108 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 52 ms 1352 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1840 ms 928 KB Output is correct
28 Execution timed out 20003 ms 25596 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 928 KB Output is correct
2 Correct 373 ms 936 KB Output is correct
3 Correct 370 ms 852 KB Output is correct
4 Correct 369 ms 924 KB Output is correct
5 Correct 360 ms 924 KB Output is correct
6 Correct 66 ms 25300 KB Output is correct
7 Correct 60 ms 25300 KB Output is correct
8 Correct 66 ms 25364 KB Output is correct
9 Correct 91 ms 26132 KB Output is correct
10 Correct 22 ms 17096 KB Output is correct
11 Correct 21 ms 17108 KB Output is correct
12 Correct 73 ms 18648 KB Output is correct
13 Correct 22 ms 17108 KB Output is correct
14 Correct 21 ms 17152 KB Output is correct
15 Correct 3844 ms 25612 KB Output is correct
16 Execution timed out 20097 ms 25780 KB Time limit exceeded
17 Halted 0 ms 0 KB -