Submission #448022

#	Time	Username	Problem	Language	Result	Execution time	Memory
448022		bigDuck	Wiring (IOI17_wiring)	C++14	13 / 100	79 ms	42992 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]=min(s[i][j]-( (s[i-1][sz[i-1] ]+(j-sz[i-1])*c[i-1][sz[i-1] ])  )+dp[i-2][sz[i-2] ], mn1[i-1][sz[i] ]+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] );
        }
    }
    precalc(i);
}







}




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});
            j++;
        }
        else{
            if(j==m){
                arr.pb({r[i], 1});
                i++;
            }
            else{
                if(r[i]<=b[j]){
                    arr.pb({r[i], 1});
                    i++;
                }
                else{
                    arr.pb({b[j], 0});
                    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(ac!=arr[i].sc){
            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