Submission #424445

#	Time	Username	Problem	Language	Result	Execution time	Memory
424445		arneves	Wiring (IOI17_wiring)	C++17	100 / 100	101 ms	31528 KiB

wiring

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

using namespace std;

typedef long long ll;
const int MX=500'005;

/*
4 5
1 2 3 7
0 4 5 9 10
*/
long long min_total_length(std::vector<int> r, std::vector<int> b) {

    ll n=r.size();
    ll m=b.size();

    //vector<ll> r,b;

    //for(auto u: rr) r.push_back(u);
    //for(auto u: bb) b.push_back(u);


    vector<pair<ll,bool>> a;
    a.push_back({-1,0});

    for(int i=0; i<n; i++){
        a.push_back({r[i],0});
    }
    for(int i=0; i<m; i++){
        a.push_back({b[i],1});
    }
    sort(a.begin(),a.end());

    ll dp[MX];
    dp[0]=0;
    ll soma_b[MX], soma_r[MX];

    for(int i=1; i<=n+m; i++){

        soma_b[i]=soma_b[i-1];
        soma_r[i]=soma_r[i-1];

        if(a[i].second){
            soma_b[i]+=a[i].first;
        }else{
            soma_r[i]+=a[i].first;
        }
    }

    //for(int i=0; i<4; i++) cout<<soma_b[i]<<' '; cout<<'\n';
    //for(int i=0; i<4; i++) cout<<soma_r[i]<<' '; cout<<'\n';

    ll temp[2*MX];
    ll indice_anterior[MX];

    for(auto &u: temp) u=-1;
    for(auto &u: indice_anterior) u=-1;
    /*
1 2
1000000000
1 2
    */

    ll j=n+m;
    temp[n+m]=0;

    for(int i=1; i<=n+m; i++){

        if(a[i].second){
            j++;
        }else{
            j--;
        }
        if(temp[j]!=-1){
            indice_anterior[i]=temp[j];
        }
        temp[j]=i;
    }

    for(int i=1; i<=n+m; i++){
        //cout<<"->"<<i<<' '<<dp[i-1]<<'\n';
        ll ans=LONG_MAX;

        if(a[i].second){

            auto u=lower_bound(r.begin(),r.end(),a[i].first);
            if(u!=r.end()) ans=min(ans,(ll)*u-a[i].first);
            if(u!=r.begin()){
                u--;
                ans=min(ans,a[i].first-(ll)*u);
            }
        }else{

            auto u=lower_bound(b.begin(),b.end(),a[i].first);
            if(u!=b.end()) ans=min(ans,(ll)*u-a[i].first);
            if(u!=b.begin()){
                u--;
                ans=min(ans,a[i].first-(ll)*u);
            }
        }
        dp[i]=dp[i-1]+ans;

        if(indice_anterior[i]!=-1){

            dp[i]=min(dp[i],dp[indice_anterior[i]]+abs((soma_r[i]-soma_r[indice_anterior[i]])-(soma_b[i]-soma_b[indice_anterior[i]])));
        }
    }
	return dp[n+m];
}

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