oj.uz

Submission #763399

# Submission time Handle Problem Language Result Execution time Memory
763399 2023-06-22T09:17:43 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 35268 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 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];
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}
 
void changeH(int P, int Q, int W) {
	hor[P][Q] = W;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}
 
void changeV(int P, int Q, int W) {
	ver[P][Q] = W;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			memo[i][j] = -1;
		}
	}
}
 
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];
		}
	}
}
 
int escape(int V1, int V2) {
	if (memo[V1][V2] == -1) {
		calc(V1);
	}
	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 20 ms 17108 KB Output is correct
2 Correct 21 ms 17100 KB Output is correct
3 Correct 74 ms 19916 KB Output is correct
4 Correct 21 ms 17108 KB Output is correct
5 Correct 21 ms 17108 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
5 Correct 0 ms 340 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 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 56 ms 1396 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 936 KB Output is correct
2 Correct 214 ms 912 KB Output is correct
3 Correct 233 ms 924 KB Output is correct
4 Correct 258 ms 912 KB Output is correct
5 Correct 240 ms 912 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 99 ms 928 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25236 KB Output is correct
2 Correct 57 ms 25408 KB Output is correct
3 Correct 59 ms 25396 KB Output is correct
4 Correct 87 ms 26700 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 936 KB Output is correct
2 Correct 216 ms 912 KB Output is correct
3 Correct 230 ms 916 KB Output is correct
4 Correct 252 ms 928 KB Output is correct
5 Correct 241 ms 852 KB Output is correct
6 Correct 58 ms 25348 KB Output is correct
7 Correct 59 ms 25408 KB Output is correct
8 Correct 56 ms 25328 KB Output is correct
9 Correct 88 ms 26852 KB Output is correct
10 Correct 21 ms 17172 KB Output is correct
11 Correct 20 ms 17092 KB Output is correct
12 Correct 76 ms 19872 KB Output is correct
13 Correct 21 ms 17140 KB Output is correct
14 Correct 20 ms 17184 KB Output is correct
15 Correct 0 ms 312 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 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 468 KB Output is correct
24 Correct 1 ms 440 KB Output is correct
25 Correct 57 ms 2720 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 96 ms 988 KB Output is correct
28 Execution timed out 20027 ms 29184 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Output is correct
2 Correct 227 ms 912 KB Output is correct
3 Correct 240 ms 932 KB Output is correct
4 Correct 259 ms 916 KB Output is correct
5 Correct 253 ms 912 KB Output is correct
6 Correct 54 ms 25300 KB Output is correct
7 Correct 55 ms 25408 KB Output is correct
8 Correct 58 ms 25428 KB Output is correct
9 Correct 90 ms 26684 KB Output is correct
10 Correct 20 ms 17180 KB Output is correct
11 Correct 20 ms 17108 KB Output is correct
12 Correct 84 ms 19836 KB Output is correct
13 Correct 25 ms 17192 KB Output is correct
14 Correct 25 ms 17108 KB Output is correct
15 Correct 2408 ms 35268 KB Output is correct
16 Execution timed out 20026 ms 33516 KB Time limit exceeded
17 Halted 0 ms 0 KB -