Submission #1053201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053201		pawned	Wiring (IOI17_wiring)	C++17	100 / 100	45 ms	12496 KiB

wiring

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
 
#include "wiring.h"
 
ll min_total_length(vector<int> r_g, vector<int> b_g) {
	vi r, b;
	for (int x : r_g)
		r.pb(x);
	for (int x : b_g)
		b.pb(x);
	int N = r.size();
	int M = b.size();
	vector<ii> vals;
	for (int i = 0; i < N; i++) {
		vals.pb({r[i], 0});
	}
	for (int i = 0; i < M; i++) {
		vals.pb({b[i], 1});
	}
	vals.pb({-1e9, -1});
	sort(vals.begin(), vals.end());
/*	cout<<"vals: ";
	for (ii p : vals)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	int K = N + M;
	vals[0].se = 1 - vals[1].se;	// opposite start as placeholder

	vi pfs(K + 1, 0);
	for (int i = 1; i <= K; i++) {
		pfs[i] = pfs[i - 1] + vals[i].fi;
	}
/*	cout<<"pfs: ";
	for (ll x : pfs)
		cout<<x<<" ";
	cout<<endl;*/
	vi dp(K + 1, 0);
	ll prev = 1;
	for (ll i = 1; i <= K; i++) {	// i = start of comp
		ll j = i;	// j = end of comp
		while (j < K && vals[j].se == vals[j + 1].se)
			j++;
		for (int k = prev; k < i; k++) {	// try connecting last comp to i
			dp[k] = min(dp[k], dp[k - 1] + (vals[i].fi - vals[k].fi));
		}
		ll minv = dp[i - 1];
		ll sum = 0;	// total connection cost to i - 1
		for (int k = i; k <= j; k++) {
			sum += (vals[k].fi - vals[i - 1].fi);
			ll vc = 2 * i - k - 1;	// paired (vc, k), (vc + 1, k - 1), up to (i - 1, i)
			if (vc >= prev) {
				ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1]);
				// toadd: extra connection cost from pairing w/ vc, vc+1, ... instead of all w/ i-1
				minv = min(minv, dp[vc - 1] + toadd);
			}
			dp[k] = minv + sum;
		}
		prev = i;
		i = j;
	}
	return dp[K];
}

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