Submission #448037

#	Time	Username	Problem	Language	Result	Execution time	Memory
448037		bigDuck	Wiring (IOI17_wiring)	C++14	13 / 100	1082 ms	69348 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<ll, ll>
#define count_bits __builtin_popcount
//#define int ll

ll n, m, g;
vector<pii> arr;
vector<ll> c[200010];
vector<ll> dp[200010];
vector<ll> mn1[200010], mn2[200010];
vector<ll> s[200010];
ll sz[200010];





void build_mn1(ll i){

    for(ll j=1; j<=sz[i]; j++){
        mn1[i][j]=dp[i][sz[i]-j ]-(s[i][sz[i] ]-s[i][sz[i]-j])+c[i][sz[i] ]*j;
        if(j>1){
            mn1[i][j]=min(mn1[i][j], mn1[i][j-1]);
        }
    }
}

void build_mn2(ll i){
    if(i<g){

    for(ll j=sz[i]; j>=1; j--){
        mn2[i][j]=dp[i][sz[i]-j ]+j*(c[i+1][1])-(s[i][sz[i] ]-s[i][sz[i]-j]  );
        if(j<sz[i]){
            mn2[i][j]=min(mn2[i][j], mn2[i][j+1]);
        }
    }

    }
}


void precalc(ll i){
build_mn1(i);
build_mn2(i);
}





void build_dp(){


for(ll i=1; i<=g; i++){
    for(ll j=1; j<=sz[i]; j++){
        s[i][j]=s[i][j-1]+c[i][j];
    }
}


for(ll j=1; j<=sz[2]; j++){
    if(j<=sz[1] ){
        dp[2][j]=s[2][j]-(s[1][sz[1]])+c[2][1]*(sz[1]-j);
    }
    else{
        dp[2][j]=s[2][j]-( s[1][sz[1] ]+(j-sz[1])*(c[1][sz[1] ])  );
    }
}
dp[2][0]=1e18;
//cout<<"ok"<<flush;
precalc(2);
//cout<<"ok"<<flush;
for(ll i=3; i<=g; i++){
    dp[i][0]=dp[i-1][sz[i-1] ];
    for(ll j=1; j<=sz[i]; j++){
        /*
        if(j>=sz[i-1]){
            dp[i][j]=mn1[i-1][sz[i-1] ]+s[i][j]-c[i-1][sz[i-1] ]*j;
        }
        else{
            dp[i][j]=min( mn1[i-1][j]+s[i][j]-j*(c[i-1][sz[i-1] ]), mn2[i-1][j+1]+s[i][j]-j*c[i][1] );
        }
        */
        dp[i][j]=1e18;
        for(int k=1; k<=sz[i-1]; k++){
            if(k<=j){
                dp[i][j]=min(dp[i][j], s[i][j]-( s[i-1][sz[i-1] ]-s[i-1][sz[i-1]-k]+(j-k)*(c[i-1][sz[i-1] ]))+dp[i-1][sz[i-1]-k ] );
            }
            else{
                dp[i][j]=min(dp[i][j], (s[i][j]+(k-j)*(c[i][1]))-(s[i-1][sz[i-1] ]-s[i-1][sz[i-1]-k ])+dp[i-1][sz[i-1]-k ] );
            }
        }

    }
    //precalc(i);
}







}




map<int, vector<int>> h1, h0;
bool v[200010];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    n=r.size(), m=b.size();
    for(ll i=0, j=0; (i<n) ||(j<m); ){
        if(i==n){
            arr.pb({b[j], 0});
            h0[b[j] ].pb(j);
            j++;
        }
        else{
            if(j==m){
                arr.pb({r[i], 1});
                h1[r[i] ].pb(i);
                i++;
            }
            else{
                if(r[i]<=b[j]){
                    arr.pb({r[i], 1});
                    h1[r[i] ].pb(i);
                    i++;
                }
                else{
                    arr.pb({b[j], 0});
                    h0[b[j] ].pb(j);
                    j++;
                }
            }
        }
    }
    g=1;
    //g++;
    c[g].pb(0);
    c[g].pb(arr[0].ft);
    for(ll i=1, ac=arr[0].sc; i<(m+n); i++){
        if(v[i]){continue;}
        if(ac!=arr[i].sc){
            if(ac==1){
                while(!h1[arr[i].ft ].empty()){
                    v[h1[arr[i].ft ].back() ]=true;
                    c[g].pb(h1[arr[i].ft ].back() );
                    h1[arr[i].ft ].pop_back();
                }
            }
            else{
                while(!h0[arr[i].ft ].empty()){
                    v[h0[arr[i].ft ].back() ]=true;
                    c[g].pb(h0[arr[i].ft ].back() );
                    h0[arr[i].ft ].pop_back();
                }
            }
            g++;
            c[g].pb(0);
            c[g].pb(arr[i].ft);
            ac=arr[i].sc;
        }
        else{
            c[g].pb(arr[i].ft);
        }
    }
    //dp[1][1]
    //cout<<"ok"<<flush;
    for(ll i=1; i<=g; i++){
        dp[i].assign(((ll)c[i].size()), 0ll);
        mn1[i].assign(((ll)c[i].size()), 0ll);
        mn2[i].assign(((ll)c[i].size()), 0ll);
        s[i].assign(((ll)c[i].size()), 0ll);
        sz[i]=c[i].size()-1;
    }
    //cout<<"ok"<<flush;

    build_dp();





	return dp[g][sz[g] ];
}

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