Submission #1045960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045960		LittleOrange	Wiring (IOI17_wiring)	C++17	20 / 100	25 ms	2660 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	ll n = r.size(),m = b.size();
	if (n<=200&&m<=200){
		vector<pair<ll,ll>> v;
		for(ll i : r) v.push_back({i,0}); 
		for(ll i : b) v.push_back({i,1}); 
		sort(v.begin(),v.end());
		ll w = n+m;
		vector<vector<ll>> dp(w,vector<ll>(w,1e18));
		for(ll i = 0;i<w-1;i++){
			if (v[i].second!=v[i+1].second){
				dp[i][i+1] = v[i+1].first-v[i].first;
			}
		}
		for(ll i = w-1;i>=0;i--){
			for(ll j = i+2;j<w;j++){
				if (v[i].second!=v[j].second){
					dp[i][j] = min(dp[i][j],(v[j].first-v[i].first)+dp[i+1][j-1]);
				}
				if (v[i].second){
					auto it = lower_bound(r.begin(),r.end(),v[i].first);
					if (it!=r.end()){
						dp[i][j] = min(dp[i][j],(*it-v[i].first)+dp[i+1][j]);
					}
				}else{
					auto it = lower_bound(b.begin(),b.end(),v[i].first);
					if (it!=b.end()){
						dp[i][j] = min(dp[i][j],(*it-v[i].first)+dp[i+1][j]);
					}
				}
				if (v[j].second){
					auto it = lower_bound(r.begin(),r.end(),v[j].first);
					if (it!=r.begin()){
						dp[i][j] = min(dp[i][j],(v[j].first-*--it)+dp[i][j-1]);
					}
				}else{
					auto it = lower_bound(b.begin(),b.end(),v[j].first);
					if (it!=b.begin()){
						dp[i][j] = min(dp[i][j],(v[j].first-*--it)+dp[i][j-1]);
					}
				}
				for(ll k = i+1;k+2<=j;k++){
					dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);
				}
			}
		}
		return dp[0][w-1];
	}
	ll c = min(n,m);
	ll ret = 0;
	for(ll i = 0;i<c;i++){
		ret += b[i]-r[i+n-c];
	}
	if (n>m){
		for(ll i = 0;i<n-m;i++){
			ret += b[0] - r[i];
		}
	}
	if(m>n){
		for(ll i = n;i<m;i++){
			ret += b[i] - r.back();
		}
	}
	return ret;
}

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