Submission #1014798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014798		hotboy2703	Wiring (IOI17_wiring)	C++17	100 / 100	38 ms	10008 KiB

wiring

#include <vector>

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

pll a[200100];
ll dist[200100];
ll sum[200100];
ll dp[200100];
const ll INF = 1e18;
long long min_total_length(std::vector<int> r, std::vector<int> b){
    ll n = sz(r)+sz(b);
    for (ll i = 1;i <= n;i ++){
        if (i <= sz(r))a[i] = MP(r[i-1],0);
        else a[i] = MP(b[i-sz(r)-1],1);
    }
    sort(a+1,a+1+n);
    {
        ll last[2] = {-1,-1};
        for (ll i = 1;i <= n;i ++){
            sum[i] = a[i].fi + sum[i-1];
            dist[i] = INF;
            if (last[1-a[i].se] != -1)dist[i] = a[i].fi - last[1-a[i].se];
            last[a[i].se] = a[i].fi;
        }
        last[0] = last[1] = -1;
        for (ll i = n;i >= 1;i --){
            if (last[1-a[i].se] != -1)dist[i] = min(dist[i],-a[i].fi + last[1-a[i].se]);
            last[a[i].se] = a[i].fi;
        }
    }
    dp[0] = 0;
    ll last = 0,cur = 0;
    for (ll i = 1;i <= n;i ++){
        if (i==1||a[i].se!=a[i-1].se){
            last=cur;
            cur=1;
        }
        else cur++;
        dp[i] = dp[i-1] + dist[i];
//        if (i==6)cout<<cur.fi<<' '<<cur.se<<' '<<last.fi<<' '<<last.se<<endl;
        if (cur <= last){
            dp[i] = min(dp[i],dp[i-cur*2] + sum[i] - sum[i-cur] - (sum[i-cur] - sum[i-cur-cur]));
        }
    }
    return dp[n];
}

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