oj.uz

Submission #1067889

# Submission time Handle Problem Language Result Execution time Memory
1067889 2024-08-21T05:20:52 Z sleepntsheep Wombats (IOI13_wombats) C++17
18 / 100
 124 ms 34060 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];
}

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9564 KB Output is correct
2 Correct 13 ms 9808 KB Output is correct
3 Correct 54 ms 12456 KB Output is correct
4 Correct 13 ms 9560 KB Output is correct
5 Correct 14 ms 9564 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6748 KB Output is correct
2 Correct 5 ms 6644 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Correct 6 ms 6652 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12120 KB Output is correct
2 Correct 57 ms 12120 KB Output is correct
3 Correct 56 ms 12120 KB Output is correct
4 Correct 89 ms 13496 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6744 KB Output is correct
2 Correct 6 ms 6692 KB Output is correct
3 Correct 6 ms 6744 KB Output is correct
4 Correct 5 ms 6744 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 56 ms 12124 KB Output is correct
7 Correct 56 ms 12120 KB Output is correct
8 Correct 56 ms 12028 KB Output is correct
9 Correct 89 ms 13396 KB Output is correct
10 Correct 13 ms 9796 KB Output is correct
11 Correct 13 ms 9804 KB Output is correct
12 Correct 47 ms 12432 KB Output is correct
13 Correct 13 ms 9564 KB Output is correct
14 Correct 13 ms 9800 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Incorrect 0 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6748 KB Output is correct
2 Correct 6 ms 6540 KB Output is correct
3 Correct 5 ms 6748 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 55 ms 12280 KB Output is correct
7 Correct 56 ms 12124 KB Output is correct
8 Correct 57 ms 12124 KB Output is correct
9 Correct 89 ms 13476 KB Output is correct
10 Correct 13 ms 9560 KB Output is correct
11 Correct 13 ms 9808 KB Output is correct
12 Correct 47 ms 12540 KB Output is correct
13 Correct 13 ms 9564 KB Output is correct
14 Correct 14 ms 9568 KB Output is correct
15 Runtime error 124 ms 34060 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -