oj.uz

Submission #762164

# Submission time Handle Problem Language Result Execution time Memory
762164 2023-06-21T02:39:53 Z SanguineChameleon Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 35228 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) {
	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 21 ms 17108 KB Output is correct
2 Correct 18 ms 17184 KB Output is correct
3 Correct 90 ms 19888 KB Output is correct
4 Correct 18 ms 17108 KB Output is correct
5 Correct 18 ms 17140 KB Output is correct
6 Correct 1 ms 308 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 1 ms 340 KB Output is correct
3 Correct 1 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 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 53 ms 2816 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 5 ms 980 KB Output is correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 4 ms 980 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 56 ms 25428 KB Output is correct
2 Correct 52 ms 25300 KB Output is correct
3 Correct 55 ms 25432 KB Output is correct
4 Correct 81 ms 26808 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1020 KB Output is correct
2 Correct 6 ms 960 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 61 ms 25444 KB Output is correct
7 Correct 55 ms 25408 KB Output is correct
8 Correct 53 ms 25444 KB Output is correct
9 Correct 100 ms 26720 KB Output is correct
10 Correct 16 ms 17176 KB Output is correct
11 Correct 18 ms 17188 KB Output is correct
12 Correct 72 ms 19956 KB Output is correct
13 Correct 16 ms 17188 KB Output is correct
14 Correct 17 ms 17108 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 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 444 KB Output is correct
20 Correct 1 ms 444 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 54 ms 2812 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 5 ms 960 KB Output is correct
28 Execution timed out 20099 ms 29164 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1108 KB Output is correct
2 Correct 6 ms 948 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 57 ms 25320 KB Output is correct
7 Correct 56 ms 25428 KB Output is correct
8 Correct 56 ms 25428 KB Output is correct
9 Correct 84 ms 26736 KB Output is correct
10 Correct 19 ms 17108 KB Output is correct
11 Correct 19 ms 17188 KB Output is correct
12 Correct 72 ms 19916 KB Output is correct
13 Correct 19 ms 17192 KB Output is correct
14 Correct 18 ms 17108 KB Output is correct
15 Correct 196 ms 35228 KB Output is correct
16 Execution timed out 20064 ms 33464 KB Time limit exceeded
17 Halted 0 ms 0 KB -