Submission #486288

#	Time	Username	Problem	Language	Result	Execution time	Memory
486288		ntabc05101	Wombats (IOI13_wombats)	C++17	100 / 100	4401 ms	105112 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 9;
const int mxR = 5000;
const int mxC = 200;
const int bs = 20;
const int mxN = mxR / 20;

int h[mxR][mxC], v[mxR][mxC];
int H[mxN << 2], L[mxN << 2];
int opt[mxC + 1];
int nds[mxN << 2][mxC][mxC];

void build(int x, int lo, int hi) {
	L[x] = lo; H[x] = hi;
	if (lo == hi) {
		return ;
	}
	int mid = (lo + hi) >> 1;
	build(x << 1, lo, mid);
	build(x << 1 | 1, mid + 1, hi);
}

void upd(int x, int l, int r) {
	if (L[x] == H[x]) {
		for (int i = 0; i < mxC; i++) {
			for (int j = 0; j < mxC; j++) {
				nds[x][i][j] = inf;
			}
		}
		for (int j = 0; j < mxC; j++) {
			nds[x][j][j] = 0;
			for (int i = L[x] * bs; i < (L[x] + 1) * bs; i++) {
				for (int k = 1; k < mxC; k++) {
					nds[x][j][k] = min(nds[x][j][k], nds[x][j][k - 1] + h[i][k - 1]);
				}
				for (int k = mxC - 1; k; k--) {
					nds[x][j][k - 1] = min(nds[x][j][k - 1], nds[x][j][k] + h[i][k - 1]);
				}
				for (int k = 0; k < mxC; k++) {
					nds[x][j][k] += v[i][k];
				}
			}
		}
		return ;
	}

	if (l <= H[x << 1]) {
		upd(x << 1, l, r);
	}
	if (H[x << 1] < r) {
		upd(x << 1 | 1, l, r);
	}

	memset(opt, 0, mxC * 4);
	for (int i = 0; i < mxC; i++) {
		for (int j = mxC - 1; ~j; j--) {
			array<int, 2> mn = {inf, 0};
			for (int k = opt[j]; k <= opt[j + 1]; k++) {
				mn = min(mn, {nds[x << 1][i][k] + nds[x << 1 | 1][k][j], -k});
			}
			nds[x][i][j] = mn[0];
			opt[j] = -mn[1];
		}
	}
}

void init(int r, int c, int H[mxR][mxC], int V[mxR][mxC]) {
	for (int i = 0; i < mxR; i++) {
		for (int j = 0; j < mxC; j++) {
			h[i][j] = inf;
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c - 1; j++) {
			h[i][j] = H[i][j];
		}
	}
	for (int i = 0; i < r - 1; i++) {
		for (int j = 0; j < c; j++) {
			v[i][j] = V[i][j];
		}
	}

	opt[mxC] = mxC - 1;
	build(1, 0, mxN - 1);
	upd(1, 0, mxN - 1);
}

void changeH(int x, int y, int w) {
	h[x][y] = w;
	upd(1, x / bs, x / bs);
}

void changeV(int x, int y, int w) {
	v[x][y] = w;
	upd(1, x / bs, x / bs);
}

int escape(int x, int y) {
	return nds[1][x][y];
}

/*
int main() {
	cin.tie(0)->sync_with_stdio(0);

	int r, c; cin >> r >> c;
	int h[r][200], v[r][200];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c - 1; j++) {
			cin >> h[i][j];
		}
	}
	for (int i = 0; i < r - 1; i++) {
		for (int j = 0; j < c; j++) {
			cin >> v[i][j];
		}
	}

	init(r, c, h, v);
	int q; cin >> q;
	while (q--) {
		int type, x, y, w; cin >> type;
		if (type == 3) {
			cin >> x >> y;
			cout << escape(x, y) << "\n";
		}
		else {
			cin >> x >> y >> w;
			//continue;
			if (type == 1) {
				changeH(x, y, w);
			}
			else {
				changeV(x, y, w);
			}
		}
	}

	return 0;
}
*/

/*
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
 */

Compilation message (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24