← Real problems

noi06p3

unratedStatement on DMOJ

CP Lang

28 lines0.3 spec
// NOI 2006 "Millennium Bug": add the fewest cells so that both side edges of
// the shape become combs, alternating protruding and recessed runs. Each side
// is a DP over (row, edge height, previous run kind, current run kind).
enum Side = Low | High

fn comb(depth: List<Int>) -> Int:
    domain I = [depth.len]
    domain H = 0..1005

    @memo(array)
    fn best(i: I, h: H, prev: Side, cur: Side) -> Int:
        if depth[i] > Int(h):
            return inf
        let j = i.next ?? return if cur == Low: 0 else: inf
        let keep = Int(h) - depth[j] + best(j, h, cur, cur)
        let step = if cur == Low: -1 else: 1
        let nudge = if prev == cur: inf else: (h + step).map(g => step + best(i, g, prev, cur)) ?? inf
        let turn_to = if cur == Low: max(Int(h) + 1, depth[j]) else: min(Int(h) - 1, depth[j])
        let flip = if cur == Low: High else: Low
        let turn = H.at(turn_to).map(g => Int(g) - depth[j] + best(j, g, cur, flip)) ?? inf
        min(keep, nudge, turn)

    best(I.first!, H(depth[I.first!]), High, Low)

let n = read<1..=1000>()
let rows = read<[n](l: 0..=1000, r: 0..=1000)>()
let reach = rows.max(by: x => x.l)!.l
print(comb(rows.map(x => reach - x.l).collect()) + comb(rows.map(x => x.r).collect()))

Accepted C++

142 lines · 0.98 s on the judge
#include "bits/extc++.h"

using namespace std;

template<class T>
using mpq = priority_queue<T, vector<T>, greater<>>;

template<class T, class U = less<T>>
using rt = __gnu_pbds::tree<T, __gnu_pbds::null_type, U, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<class T>
void dbgh(const T &t) {
	cerr << t << endl;
}

template<class T, class ...U>
void dbgh(const T &t, const U &...u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" << ": "; dbgh(__VA_ARGS__)
#else
#define cerr if(false) cerr
#define dbg(...) 1412
#endif

//imagine a language where int = long
#define long int64_t

//typing too hard
#define endl "\n"

#define sz(x) static_cast<int>((x).size())

#define inline inline __attribute__((always_inline))

const int maxn = 1e5, maxm = 25;
const bool lo = false, hi = true;

int n;
vector<int> arr;
vector<int> heights[maxn];
long memo[maxn][maxm][2];

long dp(int ind, int height, bool cur) {
	auto it = lower_bound(begin(heights[ind]), end(heights[ind]), height);
	if(it == heights[ind].end() || *it != height) {
		return 4e18;
	}

	if(ind == n - 1) {
		if(cur == lo) {
			return 0;
		}
		return 4e18;
	}

	long &ans = memo[ind][it - heights[ind].begin()][cur];
	if(ans != -1) {
		return ans;
	}
	ans = 4e18;

	// continue
	ans = min(ans, height - arr[ind + 1] + dp(ind + 1, height, cur));

	// new
	{
		bool next = cur ^ true;

		if(next == lo) {
			for(auto &a: heights[ind + 1]) {
				if(a < height) {
					ans = min(ans, a - arr[ind + 1] + dp(ind + 1, a, next));
				}
			}
		}else {
			for(auto &a: heights[ind + 1]) {
				if(a > height) {
					ans = min(ans, a - arr[ind + 1] + dp(ind + 1, a, next));
				}
			}
		}
	}

	return ans;
}

long solve(const vector<int> &_arr) {
	arr = _arr;
	n = sz(arr);

	for(int i = 0; i < n; i++) {
		heights[i].clear();

		for(int j = max(0, i - 2); j <= min(n - 1, i + 2); j++) {
			for(int k = max(arr[i], arr[j] - 2); k <= arr[j] + 2; k++) {
				heights[i].push_back(k);
			}
		}

		sort(begin(heights[i]), end(heights[i]));
		heights[i].erase(unique(begin(heights[i]), end(heights[i])), heights[i].end());
	}

	memset(memo, -1, sizeof(memo));
	long ans = 1e9;
	for(auto &a: heights[0]) {
		ans = min(ans, a - arr[0] + dp(0, a, lo));
	}
	return ans;
}

void solve() {
	cin >> n;
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	int mx = *max_element(begin(a), end(a));
	for(auto &x: a) {
		x = mx - x;
	}
	cout << solve(a) + solve(b) << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
//	cin >> t;
	for(int _ = 1; _ <= t; _++) {
		dbg(_);
//		cout << "Case #" << _ << ": ";
		solve();
	}
}