oj.uz

Submission #765163

# Submission time Handle Problem Language Result Execution time Memory
765163 2023-06-24T08:58:13 Z Sohsoh84 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 204096 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 / LIM * 2 + 5][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 16852 KB Output is correct
2 Correct 8 ms 16832 KB Output is correct
3 Correct 61 ms 19108 KB Output is correct
4 Correct 8 ms 16852 KB Output is correct
5 Correct 8 ms 16852 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 340 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 56 ms 2112 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 3660 KB Output is correct
2 Correct 880 ms 3684 KB Output is correct
3 Correct 416 ms 3664 KB Output is correct
4 Correct 389 ms 3548 KB Output is correct
5 Correct 416 ms 3640 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3588 ms 3688 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 29840 KB Output is correct
2 Correct 15 ms 29780 KB Output is correct
3 Correct 15 ms 29772 KB Output is correct
4 Correct 43 ms 31188 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 3560 KB Output is correct
2 Correct 855 ms 3636 KB Output is correct
3 Correct 398 ms 3572 KB Output is correct
4 Correct 414 ms 3768 KB Output is correct
5 Correct 385 ms 3532 KB Output is correct
6 Correct 18 ms 29800 KB Output is correct
7 Correct 15 ms 29780 KB Output is correct
8 Correct 15 ms 29856 KB Output is correct
9 Correct 42 ms 31112 KB Output is correct
10 Correct 8 ms 16852 KB Output is correct
11 Correct 7 ms 16936 KB Output is correct
12 Correct 61 ms 19104 KB Output is correct
13 Correct 8 ms 16852 KB Output is correct
14 Correct 8 ms 16832 KB Output is correct
15 Correct 0 ms 308 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 312 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 448 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 56 ms 2068 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3612 ms 3684 KB Output is correct
28 Correct 12570 ms 112608 KB Output is correct
29 Correct 5034 ms 108236 KB Output is correct
30 Incorrect 4541 ms 108168 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 3660 KB Output is correct
2 Correct 866 ms 3560 KB Output is correct
3 Correct 402 ms 3664 KB Output is correct
4 Correct 396 ms 3668 KB Output is correct
5 Correct 393 ms 3532 KB Output is correct
6 Correct 15 ms 29780 KB Output is correct
7 Correct 16 ms 29776 KB Output is correct
8 Correct 19 ms 29780 KB Output is correct
9 Correct 43 ms 31132 KB Output is correct
10 Correct 9 ms 16852 KB Output is correct
11 Correct 8 ms 16852 KB Output is correct
12 Correct 61 ms 19040 KB Output is correct
13 Correct 8 ms 16852 KB Output is correct
14 Correct 8 ms 16852 KB Output is correct
15 Correct 6525 ms 194744 KB Output is correct
16 Execution timed out 20028 ms 204096 KB Time limit exceeded
17 Halted 0 ms 0 KB -