Submission #313169

#	Time	Username	Problem	Language	Result	Execution time	Memory
313169		amunduzbaev	Wiring (IOI17_wiring)	C++14	100 / 100	76 ms	11760 KiB

wiring

//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
#define ll long long
const ll inf = 1e15,M = 2e5+5;
vector<pair<ll,bool>>v;
vector<ll> pref(M), last(M), dp(M);
vector<int> a, b;
int GM(pair<ll, bool> q) {
    ll cur = q.first;
    bool type = q.second;
    if(!type){
        auto it = lower_bound(a.begin(), a.end(), cur);
        long long mn = inf;
        if(it != a.end())
            mn = min(mn, *it - cur);
        if(it != a.begin()){
            it --;
            mn = min(mn, cur - *it);
        }
        return mn;
    }
    else{
        auto it = lower_bound(b.begin(), b.end(), cur);
        long long mn = inf;
        if(it != b.end())
            mn = min(mn, *it - cur);
        if(it != b.begin()) {
            it --;
            mn = min(mn, cur - *it);
        }
        return mn;
    }
}
ll min_total_length(vector<int> r1, vector<int> b1) {
    int n=r1.size(),m=b1.size();
    for(int i=0;i<n;i++){
        a.push_back(r1[i]);
        v.push_back({(ll)r1[i],1});
    }
    for(int i=0;i<m;i++){
        b.push_back(b1[i]);
        v.push_back({(ll)b1[i],0});
    }
    v.push_back({-inf,0});
    sort(v.begin(),v.end());
    for(int i=0;i<M;i++) last[i]=-1;
    ll cur=M/2;
    last[cur] = dp[0] = 0;
    for(int i=1;i<=n+m;i++){
        if(v[i].second){
            pref[i]=pref[i-1]+v[i].first;
            cur++;
        }
        else {
            pref[i]=pref[i-1]-v[i].first;
            cur--;
        }
        dp[i] = dp[i-1] + GM(v[i]);
        if(last[cur]!=-1)
            dp[i] = min(dp[i], dp[last[cur]] + abs(pref[i] - pref[last[cur]]));
        last[cur]=i;
    }
    ll ans=dp[n+m];
    return ans;
}
/*

4 5
1 2 3 4
5 6 7 8 9

4 5
1 2 3 7
0 4 5 8 10

*/

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