Submission #1228745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228745		PlayVoltz	Wiring (IOI17_wiring)	C++20	0 / 100	0 ms	328 KiB

wiring

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

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int min_total_length(vector<signed> r, vector<signed> b){
	vector<pii> vect(1, mp(-1, -1));
	vector<vector<int> > ooga(2);
	for (int i=0; i<r.size(); ++i)vect.pb(mp(r[i], 0)), ooga[1].pb(r[i]);
	for (int i=0; i<b.size(); ++i)vect.pb(mp(b[i], 1)), ooga[0].pb(b[i]);
	sort(vect.begin(), vect.end());
	ooga[0].pb(LLONG_MAX/2);
	ooga[0].pb(LLONG_MIN/2);
	ooga[1].pb(LLONG_MAX/2);
	ooga[1].pb(LLONG_MIN/2);
	sort(ooga[0].begin(), ooga[0].end());
	sort(ooga[1].begin(), ooga[1].end());
	vector<int> dp(vect.size(), LLONG_MAX/2);
	dp[0]=0;
	for (int i=1, p=0, sum=0; i<=vect.size(); ++i){
		dp[i]=dp[i-1]+min(*lower_bound(ooga[vect[i].se].begin(), ooga[vect[i].se].end(), vect[i].fi)-vect[i].fi, vect[i].fi-*(lower_bound(ooga[vect[i].se].begin(), ooga[vect[i].se].end(), vect[i].fi)-1));
		if (i!=1&&vect[i].se!=vect[i-1].se)p=i-1, sum=vect[i].fi-vect[i-1].fi;
		else if (p>1&&vect[p].se==vect[p-1].se)--p, sum+=vect[i].fi-vect[p].fi;
		else p=0;
		if (p)dp[i]=min(dp[i], dp[p-1]+sum);
	}
	return dp.back();
}

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