Submission #132442

#	Time	Username	Problem	Language	Result	Execution time	Memory
132442		mraron	Wiring (IOI17_wiring)	C++14	100 / 100	75 ms	10212 KiB

wiring

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

#define sz(x) (int)(x).size()
#define pb push_back

const ll inf=1LL<<38;

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pair<ll,int>> lst;
	
	for(int i=0;i<sz(r);++i) lst.emplace_back(r[i], 0);
	for(int i=0;i<sz(b);++i) lst.emplace_back(b[i], 1);
	
	sort(lst.begin(), lst.end());
	
	vector<ll> dp(sz(lst)), szum(sz(lst));
	szum[0]=lst[0].first;
	for(int i=1;i<sz(lst);++i) szum[i]+=szum[i-1]+lst[i].first;
	
	int ind=0;
	while(lst[ind].second==lst[0].second) {
		dp[ind]=inf+lst[ind].first+(ind>0?dp[ind-1]:0LL);
		ind++;
	}
	
	auto cost=[&](int l, int mid, int r) -> ll {
		ll len1=mid-l+1;
		ll len2=r-mid;
		
		ll szum1=szum[mid]-(l>0?szum[l-1]:0LL);
		ll szum2=szum[r]-szum[mid];
		
		if(len1>len2) {
			szum2+=(len1-len2)*lst[mid+1].first;
		}else {
			szum1+=(len2-len1)*lst[mid].first;
		}
		
		return szum2-szum1+(l-1>=0?dp[l-1]:0LL);
	};
	
	int prev_start=0;
	for(int i=ind;i<sz(dp);) {
		int start=i, mid=i-1, j=i-1;
		
		while(i<sz(dp) && lst[i].second==lst[start].second) {
			while(j>prev_start && cost(j,mid,i)>=cost(j-1,mid,i)) j--;
			
			dp[i]=min(cost(j,mid,i), dp[start-1]+szum[i]-szum[start-1]-lst[start-1].first*(i-start+1));
			i++;
		}
		
		prev_start=start;
	}

	//for(int i=0;i<sz(dp);++i) cerr<<dp[i]<<" \n"[i==sz(dp)-1];
	
	return dp.back();
}

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