Submission #793914

#	Time	Username	Problem	Language	Result	Execution time	Memory
793914		alvingogo	Wiring (IOI17_wiring)	C++14	100 / 100	47 ms	10832 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),from(n);
	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];
			int s=i-f[i];
			dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[f[i]-1].fs);
			from[i]=from[i-1];
			if(g[f[i]]>1){
				g[f[i]]--;
				dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[f[i]].fs);
				from[i]=from[i-1];
			}
			else{
				if(f[f[i]-1]<=f[i]-1-s){
					ll p=dp[i-1]+v[i].fs-v[f[i]-1-s].fs-dp[from[i-1]]+dp[f[i]-1-s-1];
					from[i]=f[i]-1-s-1;
					dp[i]=min(dp[i],p);
				}
			}
		}
		else{
			f[i]=i;
			if(x==i-2){
				dp[i]=min(dp[i],min(dp[i-1],dp[i-2])+(v[i].fs-v[i-1].fs));
				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);
						from[i]=j;
					}
					cnt+=v[i].fs-v[j].fs;
				}
			}
		}
		//cout << i << " " << v[i].fs << " " << dp[i] << " " << x << "\n";
	}
	return dp[n-1];
}

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