Submission #366322

#	Time	Username	Problem	Language	Result	Execution time	Memory
366322		dennisstar	Wiring (IOI17_wiring)	C++17	100 / 100	55 ms	8796 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;
using ll = long long;

const ll INF = 1e18;

ll min_total_length(vector<int> R, vector<int> B) {
	int N, M;
	N=R.size();
	M=B.size();

	vector<pair<int, int>> P;
	for (auto &i:R) P.emplace_back(i, 1);
	for (auto &i:B) P.emplace_back(i, -1);
	sort(P.begin(), P.end());
	reverse(R.begin(), R.end());
	reverse(B.begin(), B.end());

	int x=M;
	ll r=-INF, b=-INF, D=0, S=0;
	vector<pair<ll, ll>> lst(N+M+1, {INF, INF});
	lst[M]={0, 0};

	for (auto &i:P) {
		ll E=0;
		(i.se==1?R:B).pop_back();
		x+=i.se;
		S+=i.fi*i.se;
		if (i.se==1) {
			r=i.fi;
			E=D+i.fi-b;
			if (B.size()) E=min(E, D+B.back()-i.fi);
		}
		if (i.se==-1) {
			b=i.fi;
			E=D+i.fi-r;
			if (R.size()) E=min(E, D+R.back()-i.fi);
		}
		E=min(E, lst[x].fi+abs(lst[x].se-S));
		D=E;
		lst[x]={E, S};
	}

	return D;
}

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