Submission #766708

#	Time	Username	Problem	Language	Result	Execution time	Memory
766708		SanguineChameleon	Wiring (IOI17_wiring)	C++17	100 / 100	31 ms	10068 KiB

wiring

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

const long long inf = 1e18L + 20;
const int maxn = 2e5 + 20;
int pos[maxn];
int col[maxn];
long long dp[maxn];
long long pref[maxn];
long long suf[maxn];

long long min_total_length(vector<int> r, vector<int> b) {
	int n = r.size();
	int m = b.size();
	if (r[n - 1] < b[0]) {
		long long res = 0;
		for (int i = 0; i < n; i++) {
			res -= r[i];
		}
		for (int i = 0; i < m; i++) {
			res += b[i];
		}
		if (n > m) {
			res += 1LL * b[0] * (n - m);
		}
		else {
			res -= 1LL * r[n - 1] * (m - n);
		}
		return res;
	}
	n = n + m;
	for (int i = n; i >= 1; i--) {
		if (!r.empty() && (b.empty() || r.back() > b.back())) {
			pos[i] = r.back();
			col[i] = 0;
			r.pop_back();
		}
		else {
			pos[i] = b.back();
			col[i] = 1;
			b.pop_back();
		}
	}
	dp[0] = 0;
	col[0] = -1;
	col[n + 1] = -1;
	for (int i = 1; i <= n; i++) {
		dp[i] = inf;
	}
	for (int i = 2; i <= n; i++) {
		if (col[i] == col[i - 1]) {
			continue;
		}
		int lt = i - 1;
		for (; col[lt] == col[i - 1]; lt--) {
			pref[lt] = pref[lt + 1] - pos[lt] + pos[i];
			suf[lt] = suf[lt + 1] - pos[lt] + pos[i - 1];
		}
		lt++;
		for (int j = lt; j <= i; j++) {
			pref[j] += min(dp[j], dp[j - 1]);
			suf[j] += min(dp[j], dp[j - 1]);
		}
		for (int j = lt + 1; j <= i - 1; j++) {
			pref[j] = min(pref[j], pref[j - 1]);
		}
		for (int j = i - 2; j >= lt; j--) {
			suf[j] = min(suf[j], suf[j + 1]);
		}
		int rt = i;
		long long sum = 0;
		for (; col[rt] == col[i]; rt++) {
			sum += pos[rt];
			if (rt - i + 1 < i - lt) {
				dp[rt] = sum + min(suf[i - (rt - i + 1)] - 1LL * pos[i - 1] * (rt - i + 1), pref[i - (rt - i + 1)] - 1LL * pos[i] * (rt - i + 1));
			}
			else {
				dp[rt] = sum + suf[lt] - 1LL * pos[i - 1] * (rt - i + 1);
			}
		}
	}
	return dp[n];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45