oj.uz

Submission #405620

# Submission time Handle Problem Language Result Execution time Memory
405620 2021-05-16T15:18:11 Z LucaDantas Wombats (IOI13_wombats) C++17
100 / 100
 7899 ms 109776 KB 
#include "wombats.h"
#include <cstring>
#include <cstdio>

constexpr int maxm = 205, maxn = 5010, inf = 0x3f3f3f3f, SZ = 21;

struct Node
{
	int dp[maxm][maxm];
	Node() { memset(dp, 0, sizeof dp); }
};

int min(int a, int b) { return a < b ? a : b; }

int H[maxn][maxm], V[maxn][maxm];
int N, m, qtd_blocks;

void calc(int linha, Node& ans) {
	static int dp[SZ+1][maxm];
	int tam = min(SZ, N - linha);

	for(int coluna = 0; coluna < m; coluna++) {
		memset(dp, 0x3f, sizeof dp);

		dp[0][coluna] = 0;
		
		for(int i = 0; i < tam; i++) {
			for(int j = 1; j < m; j++)
				dp[i][j] = min(dp[i][j], dp[i][j-1] + H[i + linha][j-1]);

			for(int j = m-2; j >= 0; j--)
				dp[i][j] = min(dp[i][j], dp[i][j+1] + H[i + linha][j]);

			if(i < tam-1)
				for(int j = 0; j < m; j++)
					dp[i+1][j] = dp[i][j] + V[i + linha][j];
		}

		for(int i = 0; i < m; i++)
			ans.dp[coluna][i] = dp[tam-1][i];
	}
}

void merge(Node L, Node R, Node& ans) {
	auto get = [&](int INI, int FIM, int l, int r) {
		int ans = inf, opt = l;
		for(int i = l; i <= r; i++) {
			if(L.dp[INI][i] + R.dp[i][FIM] < ans)
				ans = L.dp[INI][i] + R.dp[i][FIM], opt = i;
		}
		return opt;
	};

	for(int inicio = 0; inicio < m; inicio++)
		for(int i = 0, j = m-1-inicio; j < m; i++, j++)
			ans.dp[i][j] = get(i, j, i ? ans.dp[i-1][j] : 0, j<m-1 ? ans.dp[i][j+1] : m-1);
	for(int inicio = 1; inicio < m; inicio++)
		for(int i = inicio, j = 0; i < m; i++, j++)
			ans.dp[i][j] = get(i, j, i ? ans.dp[i-1][j] : 0, j<m-1 ? ans.dp[i][j+1] : m-1);
	
	for(int i = 0; i < m; i++)
		for(int j = 0; j < m; j++)
			ans.dp[i][j] = L.dp[i][ans.dp[i][j]] + R.dp[ans.dp[i][j]][j];
}

struct SegmentTree
{
	Node tree[1<<9];
	void build(int node, int i, int j) {
		if(i == j) return (void)(calc(i*(SZ-1), tree[node]));
		int m = (i+j) >> 1;
		build(node<<1, i, m); build(node<<1|1, m+1, j);
		merge(tree[node<<1], tree[node<<1|1], tree[node]);
	}
	int query(int l, int r) { return tree[1].dp[l][r]; }
	void upd(int node, int i, int j, int pos) {
		if(i == j) return (void)(calc(i*(SZ-1), tree[node]));
		int m = (i+j) >> 1;
		if(pos <= m) upd(node<<1, i, m, pos);
		else upd(node<<1|1, m+1, j, pos);
		merge(tree[node<<1], tree[node<<1|1], tree[node]);
	}
} seg;

void init(int R, int C, int hor[5000][200], int ver[5000][200]) {
    m = C; N = R;
    for(int i = 0; i < N; i++)
    	for(int j = 0; j < m-1; j++)
    		H[i][j] = hor[i][j];
    for(int i = 0; i < N-1; i++)
    	for(int j = 0; j < m; j++)
    		V[i][j] = ver[i][j];

    qtd_blocks = (N-1) / (SZ-1);

    seg.build(1, 0, qtd_blocks);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    seg.upd(1, 0, qtd_blocks, P / (SZ-1));
    if(P % (SZ-1) == 0 && P)
    	seg.upd(1, 0, qtd_blocks, P / (SZ-1) - 1);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    seg.upd(1, 0, qtd_blocks, P / (SZ-1));
}

int escape(int V1, int V2) {
    return seg.query(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 130 ms 92740 KB Output is correct
2 Correct 137 ms 92664 KB Output is correct
3 Correct 213 ms 94376 KB Output is correct
4 Correct 163 ms 92872 KB Output is correct
5 Correct 133 ms 92736 KB Output is correct
6 Correct 39 ms 84428 KB Output is correct
7 Correct 38 ms 84444 KB Output is correct
8 Correct 40 ms 84400 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 84412 KB Output is correct
2 Correct 39 ms 84428 KB Output is correct
3 Correct 38 ms 84404 KB Output is correct
4 Correct 40 ms 84524 KB Output is correct
5 Correct 38 ms 84540 KB Output is correct
6 Correct 44 ms 84548 KB Output is correct
7 Correct 37 ms 84544 KB Output is correct
8 Correct 44 ms 84488 KB Output is correct
9 Correct 39 ms 84500 KB Output is correct
10 Correct 39 ms 84492 KB Output is correct
11 Correct 114 ms 85572 KB Output is correct
12 Correct 38 ms 84532 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 85216 KB Output is correct
2 Correct 275 ms 85260 KB Output is correct
3 Correct 278 ms 85072 KB Output is correct
4 Correct 280 ms 85188 KB Output is correct
5 Correct 281 ms 85164 KB Output is correct
6 Correct 41 ms 84428 KB Output is correct
7 Correct 38 ms 84512 KB Output is correct
8 Correct 39 ms 84472 KB Output is correct
9 Correct 1248 ms 85188 KB Output is correct
10 Correct 37 ms 84420 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 100620 KB Output is correct
2 Correct 142 ms 100664 KB Output is correct
3 Correct 163 ms 100728 KB Output is correct
4 Correct 181 ms 101420 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 85152 KB Output is correct
2 Correct 272 ms 85240 KB Output is correct
3 Correct 277 ms 85168 KB Output is correct
4 Correct 274 ms 85212 KB Output is correct
5 Correct 286 ms 85156 KB Output is correct
6 Correct 150 ms 100568 KB Output is correct
7 Correct 142 ms 100676 KB Output is correct
8 Correct 160 ms 100564 KB Output is correct
9 Correct 198 ms 101440 KB Output is correct
10 Correct 131 ms 92708 KB Output is correct
11 Correct 137 ms 92740 KB Output is correct
12 Correct 226 ms 94340 KB Output is correct
13 Correct 151 ms 92748 KB Output is correct
14 Correct 139 ms 92756 KB Output is correct
15 Correct 38 ms 84420 KB Output is correct
16 Correct 40 ms 84560 KB Output is correct
17 Correct 40 ms 84480 KB Output is correct
18 Correct 38 ms 84536 KB Output is correct
19 Correct 38 ms 84548 KB Output is correct
20 Correct 39 ms 84544 KB Output is correct
21 Correct 38 ms 84500 KB Output is correct
22 Correct 39 ms 84480 KB Output is correct
23 Correct 41 ms 84472 KB Output is correct
24 Correct 38 ms 84500 KB Output is correct
25 Correct 117 ms 85572 KB Output is correct
26 Correct 38 ms 84532 KB Output is correct
27 Correct 1210 ms 85232 KB Output is correct
28 Correct 2129 ms 101248 KB Output is correct
29 Correct 2054 ms 98428 KB Output is correct
30 Correct 2052 ms 98240 KB Output is correct
31 Correct 2157 ms 102204 KB Output is correct
32 Correct 39 ms 84424 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 85040 KB Output is correct
2 Correct 269 ms 85112 KB Output is correct
3 Correct 277 ms 85260 KB Output is correct
4 Correct 272 ms 85060 KB Output is correct
5 Correct 280 ms 85164 KB Output is correct
6 Correct 144 ms 100672 KB Output is correct
7 Correct 137 ms 100628 KB Output is correct
8 Correct 161 ms 100676 KB Output is correct
9 Correct 187 ms 101452 KB Output is correct
10 Correct 135 ms 92740 KB Output is correct
11 Correct 137 ms 92712 KB Output is correct
12 Correct 215 ms 94316 KB Output is correct
13 Correct 146 ms 92740 KB Output is correct
14 Correct 146 ms 92728 KB Output is correct
15 Correct 2299 ms 100672 KB Output is correct
16 Correct 7899 ms 103500 KB Output is correct
17 Correct 38 ms 84392 KB Output is correct
18 Correct 37 ms 84420 KB Output is correct
19 Correct 39 ms 84768 KB Output is correct
20 Correct 39 ms 84492 KB Output is correct
21 Correct 39 ms 84548 KB Output is correct
22 Correct 40 ms 84552 KB Output is correct
23 Correct 40 ms 84504 KB Output is correct
24 Correct 39 ms 84480 KB Output is correct
25 Correct 39 ms 84524 KB Output is correct
26 Correct 40 ms 84564 KB Output is correct
27 Correct 122 ms 86852 KB Output is correct
28 Correct 39 ms 84500 KB Output is correct
29 Correct 1217 ms 85248 KB Output is correct
30 Correct 2149 ms 104852 KB Output is correct
31 Correct 7709 ms 109148 KB Output is correct
32 Correct 7649 ms 108956 KB Output is correct
33 Correct 2073 ms 101652 KB Output is correct
34 Correct 7511 ms 105668 KB Output is correct
35 Correct 2092 ms 101552 KB Output is correct
36 Correct 7871 ms 105568 KB Output is correct
37 Correct 2230 ms 106460 KB Output is correct
38 Correct 7686 ms 109776 KB Output is correct
39 Correct 40 ms 84420 KB Output is correct
40 Correct 7681 ms 106092 KB Output is correct