Submission #1225469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225469		Hamed_Ghaffari	Wiring (IOI17_wiring)	C++20	100 / 100	51 ms	5048 KiB

wiring

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

using ll = long long;
using pll = pair<ll, ll>;

#define X first
#define Y second

#define mins(a, b) (a = min(a, b))

const int MXN = 2e5+5;

int n, m, a[MXN], o[MXN];
ll dp[MXN];

inline int get(int x, vector<int> &v) {
	int res = 1e9;
	int pos = lower_bound(v.begin(), v.end(), x)-v.begin();
	if(pos<v.size()) mins(res, v[pos]-x);
	if(pos>0) mins(res, x-v[pos-1]);
	return res;
}

ll min_total_length(vector<int> R, vector<int> B) {
	n = R.size(), m = B.size();
	for(int i=0; i<n; i++) a[i] = R[i];
	for(int i=0; i<m; i++) a[i+n] = B[i];
	iota(o, o+n+m, 0);
	sort(o, o+n+m, [&](int i, int j) {
		return a[i] < a[j];
	});
	sort(a, a+n+m);
	sort(R.begin(), R.end());
	sort(B.begin(), B.end());
	int id = -1;
	ll sum = 0;
	for(int i=0; i<n+m; i++) {
		dp[i+1] = dp[i] + get(a[i], o[i]<n ? B : R);
		if(i && (o[i]<n)!=(o[i-1]<n))
			sum = a[i] - a[id = i-1];
		else if(id>0 && (o[id-1]<n)==(o[id]<n))
			sum += a[i] - a[--id];
		else id = -1;
		if(id!=-1) mins(dp[i+1], dp[id]+sum);
	}
	return dp[n+m];
}

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