Submission #1236927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236927		erering	Wiring (IOI17_wiring)	C++20	100 / 100	37 ms	9132 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define pb push_back
#define ll long long
ll pref[200005];
vector<pair<ll,ll>> vec;
ll score(ll l1,ll r1,ll l2,ll r2){
    ll ans=0;
    if(r2-l2>r1-l1){
        ans+=pref[r2]-(l2>0?pref[l2-1]:0)-vec[r1].first*(r2-l2+1);
        ans+=vec[r1].first*(r1-l1+1)-(pref[r1]-(l1>0?pref[l1-1]:0));
    }
    else{
        ans+=vec[l2].first*(r1-l1+1)-(pref[r1]-(l1>0?pref[l1-1]:0));
        ans+=pref[r2]-(l2>0?pref[l2-1]:0)-vec[l2].first*(r2-l2+1);
    }
    return ans;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    for(int i=0;i<r.size();i++)vec.pb({r[i],0});
    for(int i=0;i<b.size();i++)vec.pb({b[i],1});
    sort(vec.begin(),vec.end());
    const ll N=vec.size(),inf=2e17;
    int cont[N];
    cont[0]=1; pref[0]=vec[0].first;
    for(int i=1;i<N;i++){
        pref[i]=vec[i].first+pref[i-1];
        if(vec[i].second==vec[i-1].second)cont[i]=cont[i-1]+1;
        else cont[i]=1;
    }
    ll dp[N];
    int l=-1;
    for(int i=0;i<N;i++){
        if(cont[i]==i+1){
            dp[i]=inf;
            continue;
        }
        if(cont[i-cont[i]]==i-cont[i]+1){
            dp[i]=score(0,i-cont[i],i-cont[i]+1,i);
            continue;
        }
        if(vec[i].second!=vec[i-1].second)l=i-1;
        while(l>0 && vec[l].second==vec[l-1].second && (l-2>=0?dp[l-2]:0)+score(l-1,i-cont[i],i-cont[i]+1,i)<dp[l-1]+score(l,i-cont[i],i-cont[i]+1,i))l--;
        dp[i]=score(l,i-cont[i],i-cont[i]+1,i)+min(dp[l],(l>0?dp[l-1]:0));
       // cout<<l<<endl;
    }
    return dp[N-1];
}

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