Submission #424440

#	Time	Username	Problem	Language	Result	Execution time	Memory
424440		arneves	Wiring (IOI17_wiring)	C++17	42 / 100	74 ms	15032 KiB

wiring

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

using namespace std;

typedef long long ll;
const int MX=200'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) {

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

    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;
        }
    }

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

    memset(temp,-1, sizeof(temp));
    memset(indice_anterior,-1,sizeof(indice_anterior));

    int 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=MX;

        if(a[i].second){

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

            auto u=lower_bound(b.begin(),b.end(),a[i].first);
            if(u!=b.end()) ans=min(ans,*u-a[i].first);
            if(u!=b.begin()){
                u--;
                ans=min(ans,a[i].first-*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: 0 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45