Submission #1047532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047532		ProtonDecay314	Wiring (IOI17_wiring)	C++17	100 / 100	34 ms	10028 KiB

wiring

// AM + DG

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

ll compute_cost_old(ll l, ll r, const vpll& p) {
    ll ans = 0ll;
    ll pref_color = p[l].se;

    ll fdiff = l;

    while(fdiff <= r && p[fdiff].se == pref_color) fdiff++;

    assert(fdiff <= r);

    for(ll i = l; i < fdiff; i++) {
        ans -= p[i].fi;
    }

    for(ll i = fdiff; i <= r; i++) {
        ans += p[i].fi;
    }

    ll n = fdiff - l;
    ll m = r - fdiff + 1ll;

    ans += abs(n - m) * (m > n ? -p[fdiff - 1ll].fi : p[fdiff].fi);

    return ans;
}

ll compute_cost(ll ls, ll rs, ll lsum, ll rsum, ll lend, ll rstart) {

    // cout << ls << " " << rs << " " << lsum << " " << rsum << " " << lend << " " << rstart << "\n";
    ll ans = 0ll;
    ans -= lsum;
    ans += rsum;

    ans += abs(ls - rs) * (rs > ls ? -lend : rstart);

    return ans;
}

ll min_total_length(vi r, vi b) {
	vpll p;
    int rs = r.size(), bs = b.size();
    int ri = 0, bi = 0;

    while(ri < rs && bi < bs) {
        if(r[ri] < b[bi]) {
            p.pb({r[ri], 0});
            ri++;
        } else {
            p.pb({b[bi], 1});
            bi++;
        }
    }

    while(ri < rs) {
        p.pb({r[ri], 0});
        ri++;
    }

    while(bi < bs) {
        p.pb({b[bi], 1});
        bi++;
    }

    ll MAX_DP = rs + bs;
    const ll inf = 1'000'000'000'000ll;
    vll dp(MAX_DP, inf);

    
    ll l_ind = 0ll, r_ind = -1ll, opt_split = 0ll, lsum = 0ll, rsum = 0ll;
    
    for(ll i = 1ll; i < MAX_DP; i++) {
        ll cur_color = p[i].se;
        ll j = i;

        if(cur_color != p[i - 1ll].se) {
            while(j >= 0 && p[j].se == cur_color) j--;
            r_ind = j;
            
            opt_split = j; /*Opt split has to be in [l_ind - 1, r_ind - 1]*/
            lsum = p[opt_split].fi;
            rsum = p[i].fi;
            opt_split--;

            while(j >= 0 && p[j].se != cur_color) j--;
            l_ind = j + 1ll;

            if(l_ind == 0ll) { // ! YOU ACCIDENTALLY WROTE l_ind = 0 bro
                for(ll k = 0ll; k <= opt_split; k++) {
                    lsum += p[k].fi;
                }
            }
        } else {
            rsum += p[i].fi;
        }

        if(r_ind == -1ll) {
            dp[i] = inf;
        } else if(l_ind == 0ll) {
            dp[i] = compute_cost(r_ind - l_ind + 1ll, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
        } else if(l_ind == r_ind) {
            ll min_recurs = min(dp[l_ind], (l_ind > 0ll ? dp[l_ind - 1ll] : 0ll));

            dp[i] = min_recurs + compute_cost(r_ind - l_ind + 1ll, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
        } else {
            ll cur_cost = dp[opt_split] + compute_cost(r_ind - opt_split, i - r_ind, lsum, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
            while(opt_split >= l_ind) {
                ll pot_cost = dp[opt_split - 1ll] + compute_cost(r_ind - opt_split + 1ll, i - r_ind, lsum + p[opt_split].fi, rsum, p[r_ind].fi, p[r_ind + 1ll].fi);
                // cout << "SPLIT " << opt_split << " " << cur_cost << " " << pot_cost << "\n";
                if(pot_cost < cur_cost) {
                    cur_cost = pot_cost;
                    lsum += p[opt_split].fi;
                    opt_split--;
                } else {
                    break;
                }
            }

            dp[i] = cur_cost;
        }

        // cout << dp[i] << " " << p[i].fi << " " << p[i].se << ", l = " << l_ind << " , r = " << r_ind << "\n";
    }

    return dp[MAX_DP - 1ll];
}

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