Submission #766655

#	Time	Username	Problem	Language	Result	Execution time	Memory
766655		SanguineChameleon	Wiring (IOI17_wiring)	C++17	13 / 100	1081 ms	7256 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];
int prv[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();
		}
	}
	prv[1] = 1;
	pref[1] = pos[1];
	for (int i = 2; i <= n; i++) {
		pref[i] = pref[i - 1] + pos[i];
		if (col[i] != col[i - 1]) {
			prv[i] = i;
		}
		else {
			prv[i] = prv[i - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = inf;
		if (prv[i] == 1) {
			continue;
		}
		for (int j = prv[prv[i] - 1]; j <= prv[i] - 1; j++) {
			long long dist_l = pref[prv[i] - 1] - pref[j - 1];
			long long dist_r = pref[i] - pref[prv[i] - 1];
			long long sum = dist_r - dist_l;
			if (prv[i] - j >= i - prv[i] + 1) {
				sum += pos[prv[i]] * (prv[i] - j - (i - prv[i] + 1));
			}
			else {
				sum -= pos[prv[i] - 1] * ((i - prv[i] + 1) - (prv[i] - j));
			}
			dp[i] = min(dp[i], dp[j - 1] + sum);
		}
	}
	return dp[n];
}

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