oj.uz

Submission #765179

# Submission time Handle Problem Language Result Execution time Memory
765179 2023-06-24T09:07:37 Z Sohsoh84 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 197948 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 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 7 ms 16852 KB Output is correct
2 Correct 7 ms 16852 KB Output is correct
3 Correct 65 ms 18404 KB Output is correct
4 Correct 7 ms 16852 KB Output is correct
5 Correct 7 ms 16852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 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 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 54 ms 1436 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 366 ms 3576 KB Output is correct
2 Correct 856 ms 3568 KB Output is correct
3 Correct 410 ms 3608 KB Output is correct
4 Correct 393 ms 3584 KB Output is correct
5 Correct 388 ms 3560 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3582 ms 3716 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29888 KB Output is correct
2 Correct 14 ms 29780 KB Output is correct
3 Correct 14 ms 29808 KB Output is correct
4 Correct 43 ms 30632 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 3576 KB Output is correct
2 Correct 851 ms 3660 KB Output is correct
3 Correct 407 ms 3580 KB Output is correct
4 Correct 399 ms 3584 KB Output is correct
5 Correct 399 ms 3448 KB Output is correct
6 Correct 12 ms 29780 KB Output is correct
7 Correct 16 ms 29848 KB Output is correct
8 Correct 14 ms 29832 KB Output is correct
9 Correct 54 ms 30608 KB Output is correct
10 Correct 6 ms 16904 KB Output is correct
11 Correct 6 ms 16852 KB Output is correct
12 Correct 59 ms 18416 KB Output is correct
13 Correct 12 ms 16852 KB Output is correct
14 Correct 7 ms 16852 KB Output is correct
15 Correct 0 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 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 55 ms 1484 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3659 ms 3608 KB Output is correct
28 Correct 12428 ms 112952 KB Output is correct
29 Correct 4977 ms 108796 KB Output is correct
30 Correct 4485 ms 108532 KB Output is correct
31 Correct 15745 ms 113944 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 373 ms 3608 KB Output is correct
2 Correct 854 ms 3596 KB Output is correct
3 Correct 398 ms 3580 KB Output is correct
4 Correct 389 ms 3532 KB Output is correct
5 Correct 391 ms 3476 KB Output is correct
6 Correct 14 ms 29780 KB Output is correct
7 Correct 14 ms 29780 KB Output is correct
8 Correct 14 ms 29880 KB Output is correct
9 Correct 47 ms 30668 KB Output is correct
10 Correct 7 ms 16852 KB Output is correct
11 Correct 7 ms 16808 KB Output is correct
12 Correct 60 ms 18412 KB Output is correct
13 Correct 7 ms 16852 KB Output is correct
14 Correct 7 ms 16908 KB Output is correct
15 Correct 6343 ms 196916 KB Output is correct
16 Execution timed out 20103 ms 197948 KB Time limit exceeded
17 Halted 0 ms 0 KB -