oj.uz

Submission #1067894

# Submission time Handle Problem Language Result Execution time Memory
1067894 2024-08-21T05:21:56 Z sleepntsheep Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 24232 KB 
#pragma GCC optimize("O3,unroll-loops")
#include "wombats.h"
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

#ifndef ROW
#define ROW 5000
#endif

int r, c, h[ROW][100], v[ROW][100];
int ans[100][100];


void calc_ii(int ii) {
	static int dp[2][100];
	/* find answer for (V1, V2) where V1 = ii */
	memset(dp[0], 63, sizeof dp[0]);
	dp[0][ii] = 0;
	int I = 0;
	for (int i = 0; i < r; ++i, I ^= 1) {
		static int pre[100], suf[100], ph[100]; /* annoying ahh math */ 
		ph[0] = 0;
		for (int j = 0; j + 1 < c; ++j)
			ph[j + 1] = ph[j] + h[i][j];

		pre[0] = dp[I][0];
		for (int j = 1; j < c; ++j) pre[j] = min(pre[j - 1], dp[I][j] - ph[j]);
		suf[c - 1] = dp[I][c - 1] + ph[c - 1];
		for (int j = c - 2; j >= 0; --j) suf[j] = min(suf[j + 1], dp[I][j] + ph[j]);

		for (int j = 0; j < c; ++j)
			dp[I][j] = min(ph[j] + pre[j], suf[j] - ph[j]);
		for (int j = 0; j < c; ++j)
			dp[!I][j] = dp[I][j] + v[i][j];
	}
	for (int jj = 0; jj < c; ++jj) ans[ii][jj] = dp[(r - 1) & 1][jj];
}

void calcrev_ii(int ii) {
	static int dp[2][100];
	/* find answer for (V1, V2) where V2 = ii */
	memset(dp[0], 63, sizeof dp[0]);
	dp[0][ii] = 0;
	int I = 0;
	for (int i = r - 1; i >= 0; --i, I ^= 1) {
		static int pre[100], suf[100], ph[100]; /* annoying ahh math */ 
		ph[0] = 0;
		for (int j = 0; j + 1 < c; ++j)
			ph[j + 1] = ph[j] + h[i][j];

		pre[0] = dp[I][0];
		for (int j = 1; j < c; ++j) pre[j] = min(pre[j - 1], dp[I][j] - ph[j]);
		suf[c - 1] = dp[I][c - 1] + ph[c - 1];
		for (int j = c - 2; j >= 0; --j) suf[j] = min(suf[j + 1], dp[I][j] + ph[j]);

		for (int j = 0; j < c; ++j)
			dp[I][j] = min(ph[j] + pre[j], suf[j] - ph[j]);
		if (i)
			for (int j = 0; j < c; ++j)
				dp[!I][j] = dp[I][j] + v[i - 1][j];
	}
	for (int jj = 0; jj < c; ++jj) ans[jj][ii] = dp[!I][jj];
}


void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	memset(ans, -1, sizeof ans);
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	memset(ans, -1, sizeof ans);
}

void init(int R, int C, int H[ROW][200], int V[ROW][200]) {
	srand(868686);
	r = R, c = C;
	for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j)
		v[i][j] = V[i][j];
	for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j)
		h[i][j] = H[i][j];
	memset(ans, -1, sizeof ans);
}

int escape(int V1, int V2) {
	if (ans[V1][V2] != -1) return ans[V1][V2];
	if (rand() & 1)
		calc_ii(V1);
	else
		calcrev_ii(V2);
	return ans[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 14 ms 6236 KB Output is correct
2 Correct 24 ms 6348 KB Output is correct
3 Correct 51 ms 11304 KB Output is correct
4 Correct 23 ms 9564 KB Output is correct
5 Correct 15 ms 9560 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 6516 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 62 ms 7440 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6488 KB Output is correct
2 Correct 5 ms 6492 KB Output is correct
3 Correct 6 ms 6488 KB Output is correct
4 Correct 5 ms 6668 KB Output is correct
5 Correct 9 ms 6580 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 4 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 12192 KB Output is correct
2 Correct 71 ms 12120 KB Output is correct
3 Correct 60 ms 12192 KB Output is correct
4 Correct 119 ms 12880 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6488 KB Output is correct
2 Correct 5 ms 6492 KB Output is correct
3 Correct 6 ms 6492 KB Output is correct
4 Correct 10 ms 6492 KB Output is correct
5 Correct 6 ms 6488 KB Output is correct
6 Correct 56 ms 12124 KB Output is correct
7 Correct 69 ms 12124 KB Output is correct
8 Correct 60 ms 12120 KB Output is correct
9 Correct 106 ms 12784 KB Output is correct
10 Correct 18 ms 6236 KB Output is correct
11 Correct 14 ms 9564 KB Output is correct
12 Correct 53 ms 11240 KB Output is correct
13 Correct 13 ms 9772 KB Output is correct
14 Correct 16 ms 6352 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 74 ms 7532 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct
27 Correct 4 ms 604 KB Output is correct
28 Execution timed out 20084 ms 15940 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6492 KB Output is correct
2 Correct 6 ms 6492 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 5 ms 6492 KB Output is correct
5 Correct 6 ms 6668 KB Output is correct
6 Correct 57 ms 12188 KB Output is correct
7 Correct 60 ms 12124 KB Output is correct
8 Correct 64 ms 12120 KB Output is correct
9 Correct 89 ms 12912 KB Output is correct
10 Correct 13 ms 9560 KB Output is correct
11 Correct 14 ms 9776 KB Output is correct
12 Correct 48 ms 11244 KB Output is correct
13 Correct 14 ms 9560 KB Output is correct
14 Correct 13 ms 9780 KB Output is correct
15 Runtime error 126 ms 24232 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -