oj.uz

Submission #405623

# Submission time Handle Problem Language Result Execution time Memory
405623 2021-05-16T15:21:04 Z LucaDantas Wombats (IOI13_wombats) C++17
100 / 100
 6622 ms 186412 KB 
#include "wombats.h"
#include <cstring>
#include <cstdio>

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

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<<10];
	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 207 ms 176964 KB Output is correct
2 Correct 221 ms 176960 KB Output is correct
3 Correct 288 ms 178620 KB Output is correct
4 Correct 210 ms 176892 KB Output is correct
5 Correct 196 ms 176956 KB Output is correct
6 Correct 78 ms 168696 KB Output is correct
7 Correct 77 ms 168644 KB Output is correct
8 Correct 78 ms 168644 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 168612 KB Output is correct
2 Correct 82 ms 168832 KB Output is correct
3 Correct 79 ms 168684 KB Output is correct
4 Correct 78 ms 169028 KB Output is correct
5 Correct 90 ms 169016 KB Output is correct
6 Correct 79 ms 169028 KB Output is correct
7 Correct 78 ms 169052 KB Output is correct
8 Correct 78 ms 168988 KB Output is correct
9 Correct 79 ms 169000 KB Output is correct
10 Correct 80 ms 169028 KB Output is correct
11 Correct 192 ms 170036 KB Output is correct
12 Correct 78 ms 169020 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 169284 KB Output is correct
2 Correct 228 ms 169388 KB Output is correct
3 Correct 248 ms 169412 KB Output is correct
4 Correct 252 ms 169364 KB Output is correct
5 Correct 263 ms 169252 KB Output is correct
6 Correct 79 ms 168660 KB Output is correct
7 Correct 80 ms 168772 KB Output is correct
8 Correct 83 ms 168660 KB Output is correct
9 Correct 827 ms 169364 KB Output is correct
10 Correct 77 ms 168644 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 184880 KB Output is correct
2 Correct 205 ms 184936 KB Output is correct
3 Correct 230 ms 184780 KB Output is correct
4 Correct 253 ms 185588 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 169328 KB Output is correct
2 Correct 226 ms 169356 KB Output is correct
3 Correct 251 ms 169284 KB Output is correct
4 Correct 248 ms 169444 KB Output is correct
5 Correct 240 ms 169364 KB Output is correct
6 Correct 213 ms 184884 KB Output is correct
7 Correct 223 ms 184956 KB Output is correct
8 Correct 222 ms 184884 KB Output is correct
9 Correct 253 ms 185600 KB Output is correct
10 Correct 211 ms 176952 KB Output is correct
11 Correct 202 ms 177040 KB Output is correct
12 Correct 295 ms 178464 KB Output is correct
13 Correct 218 ms 177068 KB Output is correct
14 Correct 198 ms 176960 KB Output is correct
15 Correct 76 ms 168692 KB Output is correct
16 Correct 83 ms 168668 KB Output is correct
17 Correct 92 ms 168680 KB Output is correct
18 Correct 77 ms 169084 KB Output is correct
19 Correct 79 ms 169084 KB Output is correct
20 Correct 78 ms 168992 KB Output is correct
21 Correct 79 ms 169016 KB Output is correct
22 Correct 80 ms 169012 KB Output is correct
23 Correct 80 ms 168988 KB Output is correct
24 Correct 77 ms 169028 KB Output is correct
25 Correct 159 ms 170024 KB Output is correct
26 Correct 81 ms 169008 KB Output is correct
27 Correct 831 ms 169372 KB Output is correct
28 Correct 1834 ms 185220 KB Output is correct
29 Correct 1801 ms 182420 KB Output is correct
30 Correct 1788 ms 182344 KB Output is correct
31 Correct 1880 ms 186312 KB Output is correct
32 Correct 79 ms 168612 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 169356 KB Output is correct
2 Correct 227 ms 169356 KB Output is correct
3 Correct 247 ms 169312 KB Output is correct
4 Correct 242 ms 169368 KB Output is correct
5 Correct 248 ms 169336 KB Output is correct
6 Correct 209 ms 184876 KB Output is correct
7 Correct 211 ms 184936 KB Output is correct
8 Correct 228 ms 184920 KB Output is correct
9 Correct 252 ms 185576 KB Output is correct
10 Correct 206 ms 176964 KB Output is correct
11 Correct 202 ms 176944 KB Output is correct
12 Correct 281 ms 178500 KB Output is correct
13 Correct 222 ms 176920 KB Output is correct
14 Correct 208 ms 176884 KB Output is correct
15 Correct 2512 ms 184940 KB Output is correct
16 Correct 6622 ms 186412 KB Output is correct
17 Correct 79 ms 168644 KB Output is correct
18 Correct 80 ms 168680 KB Output is correct
19 Correct 81 ms 168704 KB Output is correct
20 Correct 78 ms 169060 KB Output is correct
21 Correct 78 ms 169028 KB Output is correct
22 Correct 89 ms 169064 KB Output is correct
23 Correct 93 ms 169080 KB Output is correct
24 Correct 80 ms 169028 KB Output is correct
25 Correct 79 ms 169092 KB Output is correct
26 Correct 81 ms 169040 KB Output is correct
27 Correct 162 ms 170104 KB Output is correct
28 Correct 79 ms 168992 KB Output is correct
29 Correct 830 ms 169372 KB Output is correct
30 Correct 1866 ms 185296 KB Output is correct
31 Correct 6313 ms 185772 KB Output is correct
32 Correct 6235 ms 185576 KB Output is correct
33 Correct 1767 ms 182320 KB Output is correct
34 Correct 6273 ms 182812 KB Output is correct
35 Correct 1785 ms 182412 KB Output is correct
36 Correct 6205 ms 182732 KB Output is correct
37 Correct 1881 ms 186236 KB Output is correct
38 Correct 6267 ms 186248 KB Output is correct
39 Correct 77 ms 168644 KB Output is correct
40 Correct 6288 ms 182720 KB Output is correct