Submission #428445

#	Time	Username	Problem	Language	Result	Execution time	Memory
428445		vanic	Wiring (IOI17_wiring)	C++14	0 / 100	1092 ms	8364 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;
const ll inf=1e16;

int n, m;
pair < int, bool > svi[maxn];
ll pref[maxn];
ll dp[maxn];

inline ll dist(int ind1, int ind2){
	return abs(svi[ind1].first-svi[ind2].first);
}

ll min_total_length(vector < int > r, vector < int > b){
	n=r.size();
	m=b.size();
	for(int i=0; i<n; i++){
		svi[i]={r[i], 0};
	}
	for(int i=0; i<m; i++){
		svi[i+n]={b[i], 1};
	}
	sort(svi, svi+n+m);
	for(int i=0; i<n+m; i++){
		pref[i+1]=pref[i]+svi[i].first;
	}
	dp[1]=inf;
	int l, d;
	int br=0;
	ll curr;
	ll val;
	ll sol;
	for(int i=1; i<n+m; i++){
		if(svi[i].second!=svi[i-1].second){
			l=i-1;
			d=i-1;
			while(l>-1 && svi[l].second==svi[i-1].second){
				l--;
			}
			br=1;
		}
		if(!br){
			dp[i+1]=inf;
			continue;
		}
//		cout << l << ' ' << d << endl;
		val=0;
		for(int j=d+2; j<=i; j++){
			val+=svi[j].first-svi[d+1].first;
		}
//		cout << val << endl;
		curr=val;
		sol=inf;
//		cout << "br " << br << endl;
		for(int j=d; j>l; j--){
			if(j==d){
//				cout << curr << ' ';
				curr+=(ll)(svi[d+1].first-svi[j].first)*br;
			}
			else if(d-j<br){
//				cout << "no no no" << endl;
				curr+=svi[d].first-svi[j].first;
			}
			else{
				curr+=svi[d+1].first-svi[j].first;
			}
//			cout << curr << ' ';
			sol=min(sol, curr+dp[j]);
		}
//		cout << endl;
		dp[i+1]=sol;
		br++;
	}
/*	for(int i=0; i<=n+m; i++){
		cout << dp[i] << ' ';
	}
	cout << endl;*/
	return dp[n+m];
}

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