Submission #313253

#	Time	Username	Problem	Language	Result	Execution time	Memory
313253		talant117408	Wiring (IOI17_wiring)	C++17	100 / 100	157 ms	19064 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 2e5+7;
ll dp[N], pref[N];
map <ll, ll> last;
vector <pii> r, b, all;

ll nearest(pii p){
    ll mn = 9e18;
    if(p.second){
        auto it = lb(all(r), p);
        if(it != r.end()){
            mn = (*it).first-p.first;
        }
		if(it != r.begin()){
            it--;
            mn = min(mn, p.first-(*it).first);
        }
	}
    else{
		auto it = lb(all(b), p);
		if(it != b.end()){
            mn = (*it).first-p.first;
        }
		if(it != b.begin()){
            it--;
            mn = min(mn, p.first-(*it).first);
        }
    }
    return mn;
}

ll min_total_length(vector<int> R, vector<int> B){
    
    all.pb(mp(0, 0));
    for(auto to : R) all.pb(mp(to, 0)), r.pb(mp(to, 0));
    for(auto to : B) all.pb(mp(to, 1)), b.pb(mp(to, 1));
    sort(all(all));
    
    int n = sz(all)-1, cnt = 0, i;
    
    last[0] = dp[0] = 0;
    
    for(i = 1; i <= n; i++){
        pref[i] = pref[i-1] + ((all[i].second ? -all[i].first : all[i].first));
        cnt += all[i].second ? -1 : 1;
        dp[i] = dp[i-1]+nearest(all[i]);
        
        if(cnt == 0 || last[cnt] > 0){
            dp[i] = min(dp[i], dp[last[cnt]]+abs(pref[i]-pref[last[cnt]]));
        }
        last[cnt] = i;
    }
    
    return dp[n];
}

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