Submission #268775

#	Time	Username	Problem	Language	Result	Execution time	Memory
268775		khsoo01	Wiring (IOI17_wiring)	C++11	100 / 100	61 ms	6652 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 200005, inf = 1e9+7;

int n;
pii a[N];
ll s[N], dt[N];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	for(auto &T : r) a[++n] = {T, 0};
	for(auto &T : b) a[++n] = {T, 1};
	sort(a+1, a+1+n);
	a[0] = {-inf, 1-a[1].Y};
	for(int i=1;i<=n;i++) {
		s[i] = s[i-1] + a[i].X;
	}
	for(int i=1,p=1;i<=n;i++) {
		int j = i;
		while(j<n && a[j+1].Y == a[i].Y) j++;
		for(int k=p;k<i;k++) {
			dt[k] = min(dt[k], dt[k-1] + a[i].X - a[k].X);
		}
		ll C = 0, M = dt[i-1];
		for(int k=i;k<=j;k++) {
			C += a[k].X - a[i-1].X;
			int X = 2*i-2-k;
			if(X+1 >= p) {
				M = min(M, dt[X] + 1ll * a[i-1].X * (i-1-X) - s[i-1] + s[X]);
			}
			dt[k] = C + M;
		}
		p = i;
		i = j;
	}
	return dt[n];
}

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