oj.uz

Submission #763404

# Submission time Handle Problem Language Result Execution time Memory
763404 2023-06-22T09:20:01 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26240 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxN = 5e3 + 20;
const int maxM = 2e2 + 20;
int hor[5020][220];
int ver[5020][220];
int memo[220][220];
int tmp[5020][220];
int dp[5020][220];
int N, M;
 

void calc(int X) {
	for (X = 0; X < M; X++) {
		dp[0][X] = 0;
		for (int i = X - 1; i >= 0; i--) {
			dp[0][i] = dp[0][i + 1] + hor[0][i];
		}
		for (int i = X + 1; i < M; i++) {
			dp[0][i] = dp[0][i - 1] + hor[0][i - 1];
		}
		for (int i = 1; i < N; 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 i = 0; i < M; i++) {
			memo[X][i] = dp[N - 1][i];
		}
	}
}

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);
}

void changeH(int P, int Q, int W) {
	hor[P][Q] = W;
	calc(-1);
}
 
void changeV(int P, int Q, int W) {
	ver[P][Q] = W;
	calc(-1);
}
 
 
int escape(int V1, int V2) {
	return memo[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 21 ms 17164 KB Output is correct
2 Correct 19 ms 17108 KB Output is correct
3 Correct 77 ms 18792 KB Output is correct
4 Correct 29 ms 17108 KB Output is correct
5 Correct 21 ms 17192 KB Output is correct
6 Correct 1 ms 312 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 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 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 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 63 ms 1372 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 393 ms 912 KB Output is correct
2 Correct 362 ms 916 KB Output is correct
3 Correct 389 ms 916 KB Output is correct
4 Correct 397 ms 920 KB Output is correct
5 Correct 363 ms 916 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1852 ms 916 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25352 KB Output is correct
2 Correct 85 ms 25408 KB Output is correct
3 Correct 75 ms 25428 KB Output is correct
4 Correct 88 ms 26240 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 920 KB Output is correct
2 Correct 360 ms 916 KB Output is correct
3 Correct 387 ms 936 KB Output is correct
4 Correct 375 ms 852 KB Output is correct
5 Correct 371 ms 916 KB Output is correct
6 Correct 73 ms 25352 KB Output is correct
7 Correct 55 ms 25412 KB Output is correct
8 Correct 62 ms 25444 KB Output is correct
9 Correct 107 ms 26184 KB Output is correct
10 Correct 20 ms 17088 KB Output is correct
11 Correct 23 ms 17124 KB Output is correct
12 Correct 78 ms 18808 KB Output is correct
13 Correct 24 ms 17140 KB Output is correct
14 Correct 31 ms 17088 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 444 KB Output is correct
19 Correct 1 ms 480 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 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 74 ms 1568 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1907 ms 1008 KB Output is correct
28 Execution timed out 20036 ms 25604 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 912 KB Output is correct
2 Correct 364 ms 924 KB Output is correct
3 Correct 372 ms 852 KB Output is correct
4 Correct 377 ms 916 KB Output is correct
5 Correct 367 ms 920 KB Output is correct
6 Correct 78 ms 25300 KB Output is correct
7 Correct 79 ms 25404 KB Output is correct
8 Correct 77 ms 25428 KB Output is correct
9 Correct 101 ms 26188 KB Output is correct
10 Correct 24 ms 17108 KB Output is correct
11 Correct 24 ms 17108 KB Output is correct
12 Correct 78 ms 18828 KB Output is correct
13 Correct 26 ms 17088 KB Output is correct
14 Correct 29 ms 17164 KB Output is correct
15 Correct 3810 ms 25652 KB Output is correct
16 Execution timed out 20009 ms 25724 KB Time limit exceeded
17 Halted 0 ms 0 KB -