Submission #1047157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047157		ProtonDecay314	Wiring (IOI17_wiring)	C++17	17 / 100	1095 ms	10152 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(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 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;
    vll dp(MAX_DP, INF(ll));

    const ll inf = 1'000'000'000'000ll;

    for(ll i = 0; i < MAX_DP; i++) {
        ll cur_color = p[i].se;
        ll j = i;

        while(j >= 0 && p[j].se == cur_color) j--;
        ll r_ind = j;

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

        if(r_ind == -1ll) {
            dp[i] = inf;
        } else if(l_ind == 0ll) {
            dp[i] = compute_cost(l_ind, i, p);
        } else if(l_ind == r_ind) {
            dp[i] = min(dp[l_ind], (l_ind > 0ll ? dp[l_ind - 1ll] : 0ll)) + compute_cost(l_ind, i, p);
        } else {
            for(ll k = l_ind - 1ll; k <= r_ind - 1ll; k++) {
                dp[i] = min(dp[i], (k < 0ll ? 0ll : dp[k]) + compute_cost(k + 1ll, i, p));
            }
        }

        // 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: 0 / 13
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45