oj.uz

Submission #765217

# Submission time Handle Problem Language Result Execution time Memory
765217 2023-06-24T09:26:25 Z Sohsoh84 Wombats (IOI13_wombats) C++17
100 / 100
 18597 ms 231920 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 5000 + 10;
const ll MAXM = 200 + 10;
const ll INF = 1e9 + 10;
const ll LIM = 10;

int n, m, H[MAXN][MAXM], V[MAXN][MAXM], ps[MAXN][MAXM], sg[MAXN][MAXM][MAXM], opt[MAXM][MAXM], 
    lc[MAXN << 1], rc[MAXN << 1], sgsz = 1, dist[MAXN][MAXM];

inline void update_ps(int i) {
	for (int j = 2; j <= m; j++)
		ps[i][j] = ps[i][j - 1] + H[i][j - 1];
}

inline vector<vector<int>> fuck(int l, int r) {
	vector<vector<int>> ans;
	ans.resize(MAXN);
	for (auto& e : ans) e.resize(MAXM);

	if (l == r) {
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++)
				ans[i][j] = ps[l][max(i, j)] - ps[l][min(i, j)];
		
		return ans;
	}

	int mid = (l + r) >> 1;
	vector<vector<int>> A = fuck(l, mid), B = fuck(mid + 1, r);
	
	for (int i = 1; i <= m; i++) {
		opt[i][m + 1] = m;
		opt[0][i] = 1;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = m; j > 0; j--) {
			int optl = opt[i - 1][j], optr = opt[i][j + 1];
			ans[i][j] = INF;
			opt[i][j] = optl;

			for (int t = optl; t <= optr; t++) {
				int cost = A[i][t] + V[mid][t] + B[t][j];
				if (cost < ans[i][j]) {
					ans[i][j] = cost;
					opt[i][j] = t;
				}
			}
		}
	}

	return ans;
}

inline void tof(int l, int r, int v) {
	vector<vector<int>> ans = fuck(l, r);
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			sg[v][i][j] = ans[i][j];
}

inline void update_ans(int mid, int v) { // opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
	for (int i = 1; i <= m; i++) {
		opt[i][m + 1] = m;
		opt[0][i] = 1;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = m; j > 0; j--) {
			int optl = opt[i - 1][j], optr = opt[i][j + 1];
			sg[v][i][j] = INF;
			opt[i][j] = optl;

			for (int t = optl; t <= optr; t++) {
				int cost = sg[lc[v]][i][t] + V[mid][t] + sg[rc[v]][t][j];
				if (cost < sg[v][i][j]) {
					sg[v][i][j] = cost;
					opt[i][j] = t;
				}
			}
		}
	}
}

void build(int l = 1, int r = n, int v = 1) {
	if (r - l + 1 <= LIM) {
		tof(l, r, v);
	} else {
		int mid = (l + r) >> 1;
		lc[v] = ++sgsz;
		rc[v] = ++sgsz;
		build(l, mid, lc[v]);
		build(mid + 1, r, rc[v]);
		update_ans(mid, v);
	}
}

void update(int ind, int l = 1, int r = n, int v = 1) {
	if (r - l + 1 <= LIM) {
		tof(l, r, v);
	} else {
		int mid = (l + r) >> 1;
		if (ind <= mid) update(ind, l, mid, lc[v]);
		else update(ind, mid + 1, r, rc[v]);
		
		update_ans(mid, v);
	}
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
	n = R_, m = C_;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			H[i][j] = H_[i - 1][j - 1];
	
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			V[i][j] = V_[i - 1][j - 1];

	for (int i = 1; i <= n; i++)
		update_ps(i);
	
	build();
}

void changeH(int P, int Q, int W) {
	P++, Q++;
	H[P][Q] = W;
	update_ps(P);
	update(P);
}

void changeV(int P, int Q, int W) {
	P++, Q++;
	V[P][Q] = W;
	update(P);
}

int escape(int V1, int V2) {
	V1++, V2++;
	return sg[1][V1][V2];
}

// TODO: 1-base
// TODO: check fit in ll
// TODO: change max limits
// TODO: check n == 1
// TODO: check bounds(n / m)

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 14309 ms 42820 KB Output is correct
2 Correct 14364 ms 42908 KB Output is correct
3 Correct 14347 ms 42848 KB Output is correct
4 Correct 14646 ms 42832 KB Output is correct
5 Correct 14378 ms 43116 KB Output is correct
6 Correct 6 ms 13140 KB Output is correct
7 Correct 6 ms 13140 KB Output is correct
8 Correct 6 ms 13104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13140 KB Output is correct
2 Correct 6 ms 13140 KB Output is correct
3 Correct 7 ms 13140 KB Output is correct
4 Correct 35 ms 30408 KB Output is correct
5 Correct 38 ms 30436 KB Output is correct
6 Correct 38 ms 30360 KB Output is correct
7 Correct 37 ms 30404 KB Output is correct
8 Correct 35 ms 30436 KB Output is correct
9 Correct 37 ms 30364 KB Output is correct
10 Correct 37 ms 30384 KB Output is correct
11 Correct 93 ms 30396 KB Output is correct
12 Correct 38 ms 30396 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 29260 KB Output is correct
2 Correct 1076 ms 29380 KB Output is correct
3 Correct 1102 ms 29444 KB Output is correct
4 Correct 1136 ms 29356 KB Output is correct
5 Correct 1128 ms 29288 KB Output is correct
6 Correct 6 ms 13140 KB Output is correct
7 Correct 6 ms 13140 KB Output is correct
8 Correct 6 ms 13140 KB Output is correct
9 Correct 4847 ms 29348 KB Output is correct
10 Correct 15 ms 17448 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14109 ms 55960 KB Output is correct
2 Correct 14338 ms 55996 KB Output is correct
3 Correct 14476 ms 55864 KB Output is correct
4 Correct 14249 ms 56684 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 29288 KB Output is correct
2 Correct 1086 ms 29396 KB Output is correct
3 Correct 1116 ms 29284 KB Output is correct
4 Correct 1122 ms 29440 KB Output is correct
5 Correct 1126 ms 29252 KB Output is correct
6 Correct 14502 ms 55908 KB Output is correct
7 Correct 14390 ms 55812 KB Output is correct
8 Correct 14558 ms 55828 KB Output is correct
9 Correct 14783 ms 56664 KB Output is correct
10 Correct 15039 ms 42868 KB Output is correct
11 Correct 14784 ms 42860 KB Output is correct
12 Correct 14766 ms 42952 KB Output is correct
13 Correct 14548 ms 42852 KB Output is correct
14 Correct 14529 ms 42828 KB Output is correct
15 Correct 6 ms 13140 KB Output is correct
16 Correct 6 ms 13024 KB Output is correct
17 Correct 6 ms 13100 KB Output is correct
18 Correct 40 ms 30372 KB Output is correct
19 Correct 37 ms 30388 KB Output is correct
20 Correct 36 ms 30404 KB Output is correct
21 Correct 37 ms 30388 KB Output is correct
22 Correct 33 ms 30364 KB Output is correct
23 Correct 33 ms 30396 KB Output is correct
24 Correct 50 ms 30372 KB Output is correct
25 Correct 88 ms 30408 KB Output is correct
26 Correct 35 ms 30432 KB Output is correct
27 Correct 4856 ms 29416 KB Output is correct
28 Correct 14896 ms 139176 KB Output is correct
29 Correct 12761 ms 135672 KB Output is correct
30 Correct 12575 ms 135436 KB Output is correct
31 Correct 15948 ms 140096 KB Output is correct
32 Correct 16 ms 17448 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1028 ms 29484 KB Output is correct
2 Correct 1101 ms 29308 KB Output is correct
3 Correct 1151 ms 29440 KB Output is correct
4 Correct 1129 ms 29364 KB Output is correct
5 Correct 1120 ms 29476 KB Output is correct
6 Correct 14512 ms 55980 KB Output is correct
7 Correct 14851 ms 55836 KB Output is correct
8 Correct 15519 ms 55876 KB Output is correct
9 Correct 15100 ms 56664 KB Output is correct
10 Correct 15442 ms 42852 KB Output is correct
11 Correct 15012 ms 42824 KB Output is correct
12 Correct 14597 ms 42844 KB Output is correct
13 Correct 14560 ms 42800 KB Output is correct
14 Correct 14493 ms 42884 KB Output is correct
15 Correct 8397 ms 223080 KB Output is correct
16 Correct 18597 ms 225188 KB Output is correct
17 Correct 7 ms 13140 KB Output is correct
18 Correct 6 ms 13104 KB Output is correct
19 Correct 6 ms 13140 KB Output is correct
20 Correct 39 ms 30392 KB Output is correct
21 Correct 40 ms 30376 KB Output is correct
22 Correct 39 ms 30416 KB Output is correct
23 Correct 38 ms 30384 KB Output is correct
24 Correct 37 ms 30364 KB Output is correct
25 Correct 37 ms 30340 KB Output is correct
26 Correct 38 ms 30376 KB Output is correct
27 Correct 117 ms 30504 KB Output is correct
28 Correct 40 ms 30400 KB Output is correct
29 Correct 4994 ms 29444 KB Output is correct
30 Correct 15704 ms 142592 KB Output is correct
31 Correct 17856 ms 231208 KB Output is correct
32 Correct 17921 ms 231312 KB Output is correct
33 Correct 13424 ms 138728 KB Output is correct
34 Correct 15112 ms 227192 KB Output is correct
35 Correct 13178 ms 138928 KB Output is correct
36 Correct 15098 ms 227276 KB Output is correct
37 Correct 15597 ms 144564 KB Output is correct
38 Correct 17919 ms 231920 KB Output is correct
39 Correct 15 ms 17448 KB Output is correct
40 Correct 15395 ms 227288 KB Output is correct