Submission #749835

#	Time	Username	Problem	Language	Result	Execution time	Memory
749835		grogu	Wiring (IOI17_wiring)	C++14	100 / 100	44 ms	10060 KiB

wiring

#include "wiring.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
#define maxn 200005
ll n;
pll a[maxn];
ll last[2];
ll dp[maxn];
ll ps[maxn];
ll sum = 0;
bool ok;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    for(ll x : r) a[++n] = {x,0};
    for(ll x : b) a[++n] = {x,1};
    sort(a+1,a+1+n);
    a[0].sc = 2;
    sum = 0;
    for(ll i = 1;i<=n;i++){
        dp[i] = llinf;
        if(!last[a[i].sc^1]){last[a[i].sc] = i;continue;}
        if(a[i].sc!=a[i-1].sc){
            dp[i] = dp[i-1] + a[i].fi - a[i-1].fi;
            ll cur = 0;
            for(ll j = i-1;j>last[a[i].sc];j--){
                cur+=a[i].fi-a[j].fi;
                ps[j] = dp[j-1] + cur;
            }
            for(ll j = last[a[i].sc]+2;j<i;j++) ps[j] = min(ps[j],ps[j-1]);
            dp[i] = min(dp[i],ps[i-1]);
            ok = 1;
            sum = 0;
        }else{
            dp[i] = min(dp[i],dp[i-1] + a[i].fi - a[last[a[i].sc^1]].fi);
            sum+= a[i].fi - a[last[a[i].sc^1]+1].fi;
            ll sz = i-last[a[i].sc^1];
            if(ok&&(a[i].sc^1)==a[last[a[i].sc^1]-sz+1].sc){
                dp[i] = min(dp[i],ps[last[a[i].sc^1]-sz+1] + sum);
            }else ok = 0;
        }
        last[a[i].sc] = i;
    }
	return dp[n];
}
/**
4 5
1 2 3 7
0 4 5 9 10
**/

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