Submission #793876

#	Time	Username	Problem	Language	Result	Execution time	Memory
793876		alvingogo	Wiring (IOI17_wiring)	C++14	38 / 100	33 ms	8124 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

typedef long long ll;
const ll inf=1e15;
ll min_total_length(vector<int> r, vector<int> b) {
	vector<pair<ll,int> > v;
	v.push_back({-inf,0});
	v.push_back({-inf,1});
	for(auto h:r){
		v.push_back({h,0});
	}
	for(auto h:b){
		v.push_back({h,1});
	}
	sort(v.begin(),v.end());
	int n=v.size();
	int l[2]={0,1};
	vector<ll> dp(n,inf);
	vector<int> f(n,0),g(n,0);
	dp[1]=0;
	f[1]=1;
	for(int i=2;i<n;i++){
		int x=l[v[i].sc];
		l[v[i].sc]=i;
		if(x==i-1){
			f[i]=f[i-1];
			dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[l[v[i].sc^1]].fs);
			if(g[f[i]]>1){
				g[f[i]]--;
				dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[f[i]].fs);
			}
		}
		else{
			f[i]=i;
			if(x==i-2){
				dp[i]=min(dp[i],dp[i-1]+(v[i].fs-v[i-1].fs));
				dp[i]=min(dp[i],v[i].fs-v[i-1].fs+dp[i-2]);
				g[i]=1;
			}
			else{
				ll cnt=v[i].fs-v[i-1].fs;
				for(int j=i-2;j>=x;j--){
					if(dp[j]+cnt<=dp[i]){
						dp[i]=min(dp[i],dp[j]+cnt);
						g[i]=(i-j-1);
					}
					cnt+=v[i].fs-v[j].fs;
				}
			}
		}
		//cout << i << " " << v[i].fs << " " << dp[i] << " " << x << "\n";
	}
	return dp[n-1];
}

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