oj.uz

Submission #765234

# Submission time Handle Problem Language Result Execution time Memory
765234 2023-06-24T09:35:18 Z Sohsoh84 Wombats (IOI13_wombats) C++17
76 / 100
 10125 ms 262144 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 = 8;

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 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;
				}
			}
		}
	}
}

inline void dijkstra(int x, int y, int r) {
	priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
	for (int i = x; i <= r; i++)
		for (int j = 1; j <= m; j++)
			dist[i][j] = INF;

	dist[x][y] = 0;
	pq.push({dist[x][y], {x, y}});

	while (!pq.empty()) {
		auto [d, pos] = pq.top();
		pq.pop();
		auto [x, y] = pos;
		if (dist[x][y] != d) continue;

		if (x < r && dist[x + 1][y] > dist[x][y] + V[x][y]) {
			dist[x + 1][y] = dist[x][y] + V[x][y];
			pq.push({dist[x + 1][y], {x + 1, y}});
		}

		if (y > 1 && dist[x][y - 1] > dist[x][y] + H[x][y - 1]) {
			dist[x][y - 1] = dist[x][y] + H[x][y - 1];
			pq.push({dist[x][y - 1], {x, y - 1}});
		}

		if (y < m && dist[x][y + 1] > dist[x][y] + H[x][y]) {
			dist[x][y + 1] = dist[x][y] + H[x][y];
			pq.push({dist[x][y + 1], {x, y + 1}});
		}
	}
}

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

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 9 ms 21332 KB Output is correct
2 Correct 10 ms 21288 KB Output is correct
3 Correct 62 ms 23020 KB Output is correct
4 Correct 9 ms 21352 KB Output is correct
5 Correct 8 ms 21360 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 57 ms 1700 KB Output is correct
12 Correct 2 ms 596 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 3572 KB Output is correct
2 Correct 862 ms 3568 KB Output is correct
3 Correct 399 ms 3588 KB Output is correct
4 Correct 401 ms 3584 KB Output is correct
5 Correct 399 ms 3560 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3655 ms 3584 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35180 KB Output is correct
2 Correct 16 ms 35188 KB Output is correct
3 Correct 17 ms 35076 KB Output is correct
4 Correct 44 ms 36044 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 3572 KB Output is correct
2 Correct 868 ms 3564 KB Output is correct
3 Correct 408 ms 3584 KB Output is correct
4 Correct 401 ms 3584 KB Output is correct
5 Correct 399 ms 3552 KB Output is correct
6 Correct 15 ms 35156 KB Output is correct
7 Correct 15 ms 35148 KB Output is correct
8 Correct 16 ms 35172 KB Output is correct
9 Correct 48 ms 36040 KB Output is correct
10 Correct 8 ms 21332 KB Output is correct
11 Correct 11 ms 21360 KB Output is correct
12 Correct 62 ms 23044 KB Output is correct
13 Correct 8 ms 21332 KB Output is correct
14 Correct 8 ms 21332 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 59 ms 1800 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 3618 ms 3608 KB Output is correct
28 Correct 7559 ms 201280 KB Output is correct
29 Correct 5000 ms 109356 KB Output is correct
30 Correct 4519 ms 109352 KB Output is correct
31 Correct 10125 ms 202560 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 3656 KB Output is correct
2 Correct 871 ms 3636 KB Output is correct
3 Correct 424 ms 3664 KB Output is correct
4 Correct 409 ms 3660 KB Output is correct
5 Correct 403 ms 3636 KB Output is correct
6 Correct 18 ms 35156 KB Output is correct
7 Correct 18 ms 35156 KB Output is correct
8 Correct 17 ms 35172 KB Output is correct
9 Correct 46 ms 36248 KB Output is correct
10 Correct 12 ms 21332 KB Output is correct
11 Correct 10 ms 21332 KB Output is correct
12 Correct 63 ms 23452 KB Output is correct
13 Correct 9 ms 21344 KB Output is correct
14 Correct 10 ms 21332 KB Output is correct
15 Runtime error 3737 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -