oj.uz

Submission #765187

# Submission time Handle Problem Language Result Execution time Memory
765187 2023-06-24T09:12:43 Z Sohsoh84 Wombats (IOI13_wombats) C++17
76 / 100
 10088 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 = 6;

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 8 ms 21356 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 68 ms 22888 KB Output is correct
4 Correct 10 ms 21332 KB Output is correct
5 Correct 9 ms 21332 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 0 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 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 55 ms 1556 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 363 ms 4092 KB Output is correct
2 Correct 711 ms 4072 KB Output is correct
3 Correct 328 ms 4268 KB Output is correct
4 Correct 315 ms 4240 KB Output is correct
5 Correct 309 ms 4240 KB Output is correct
6 Correct 1 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 2927 ms 4280 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 15 ms 35148 KB Output is correct
2 Correct 15 ms 35160 KB Output is correct
3 Correct 16 ms 35088 KB Output is correct
4 Correct 44 ms 35868 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 4092 KB Output is correct
2 Correct 714 ms 4076 KB Output is correct
3 Correct 334 ms 4264 KB Output is correct
4 Correct 318 ms 4264 KB Output is correct
5 Correct 310 ms 4240 KB Output is correct
6 Correct 16 ms 35172 KB Output is correct
7 Correct 16 ms 35156 KB Output is correct
8 Correct 17 ms 35156 KB Output is correct
9 Correct 43 ms 35888 KB Output is correct
10 Correct 9 ms 21332 KB Output is correct
11 Correct 8 ms 21344 KB Output is correct
12 Correct 62 ms 22876 KB Output is correct
13 Correct 9 ms 21332 KB Output is correct
14 Correct 9 ms 21460 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 58 ms 1484 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2830 ms 4280 KB Output is correct
28 Correct 7512 ms 200948 KB Output is correct
29 Correct 3055 ms 196608 KB Output is correct
30 Correct 2863 ms 196632 KB Output is correct
31 Correct 10088 ms 201968 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 3988 KB Output is correct
2 Correct 715 ms 4076 KB Output is correct
3 Correct 348 ms 4268 KB Output is correct
4 Correct 321 ms 4264 KB Output is correct
5 Correct 323 ms 4264 KB Output is correct
6 Correct 15 ms 35156 KB Output is correct
7 Correct 20 ms 35096 KB Output is correct
8 Correct 17 ms 35064 KB Output is correct
9 Correct 45 ms 35952 KB Output is correct
10 Correct 11 ms 21312 KB Output is correct
11 Correct 8 ms 21360 KB Output is correct
12 Correct 61 ms 22848 KB Output is correct
13 Correct 8 ms 21264 KB Output is correct
14 Correct 8 ms 21284 KB Output is correct
15 Runtime error 3676 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -