Submission #1256216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256216		biank	Wiring (IOI17_wiring)	C++20	100 / 100	26 ms	8256 KiB

wiring

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

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const ll INF = 1e18;

ll min_total_length(vi r, vi b) {
    vector<pair<vi, bool>> groups;
    for (int i = 0, j = 0; i < sz(r) || j < sz(b); ) {
        if (j >= sz(b) || (i < sz(r) && r[i] < b[j])) {
            if (groups.empty() || groups.back().snd) groups.eb(vi{r[i]}, false);
            else groups.back().fst.pb(r[i]);
            i++;
        } else {
            if (groups.empty() || !groups.back().snd) groups.eb(vi{b[j]}, true);
            else groups.back().fst.pb(b[j]);
            j++;
        }
    }
    vll dp(sz(groups[0].fst) + 1, INF);
    dp[0] = 0;
    forsn(g, 1, sz(groups)) {
        auto &pos = groups[g].fst;
        auto &prevPos = groups[g - 1].fst;
        int n = sz(pos), m = sz(prevPos);
        int dist = pos.front() - prevPos.back();
        vll suff(m + 1);
        suff[m] = 0LL;
        dforn(i, m) suff[i] = suff[i + 1] + prevPos.back() - prevPos[i];
        vll pref(n + 1);
        pref[0] = 0LL;
        forn(i, n) pref[i + 1] = pref[i] + pos[i] - pos.front();
        vll bestPref(m + 1), bestSuff(m + 1);
        forn(i, m + 1) {
            bestPref[i] = dp[m - i] + suff[m - i];
            bestSuff[i] = dp[m - i] + suff[m - i] + 1LL * i * dist;
        }
        forsn(i, 1, m + 1) bestPref[i] = min(bestPref[i], bestPref[i - 1]);
        dforn(i, m) bestSuff[i] = min(bestSuff[i], bestSuff[i + 1]);
        vll newDP(sz(pos) + 1, INF);
        forn(i, sz(pos) + 1) {
            newDP[i] = pref[i] + 1LL * i * dist + bestPref[min(i, sz(prevPos))]; 
            if (i < sz(prevPos)) newDP[i] = min(newDP[i], pref[i] + bestSuff[i + 1]);
        }
        dp = newDP;
    }
    return dp.back();
}

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