Submission #1298117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298117		Lithanium	Wiring (IOI17_wiring)	C++20	0 / 100	1 ms	344 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;

using ll = long long;

const int MAXN = 200005;
const ll INF = (1LL<<60);

ll dp[MAXN];
ll psa[MAXN];
pair<ll,int> dt[MAXN]; // 1-indexed
int N_global;          // if you need global elsewhere, but we'll set/reset it

long long min_total_length(vector<int> R, vector<int> B) {
    // --- INITIALIZE ---
    N_global = 0;               // CRITICAL: reset N before filling dt
    for (int x : R) dt[++N_global] = {x, 1};
    for (int x : B) dt[++N_global] = {x, -1};
    sort(dt + 1, dt + 1 + N_global);

    // prefix sum of positions
    psa[0] = 0;
    for (int i = 1; i <= N_global; ++i) psa[i] = psa[i-1] + dt[i].first;

    // dp init
    for (int i = 0; i <= N_global; ++i) dp[i] = INF;
    dp[0] = 0;

    // iterate chunks of equal color
    int prev = 1; // start index of previous chunk
    int l = 1;
    while (l <= N_global) {
        int r = l;
        while (r <= N_global && dt[r].second == dt[l].second) ++r;
        // chunk is [l, r)  (r is first index after chunk)

        // 1) pair elements of this chunk with the next chunk's first element
        if (r <= N_global) {
            for (int i = l; i < r; ++i) {
                // dp[i] can be formed by pairing i with dt[r].first and using dp[i-1]
                dp[i] = min(dp[i], dp[i-1] + (dt[r].first - dt[i].first));
            }
        }

        // 2) pair elements of this chunk with previous elements
        if (l != 1) {
            // Precompute the base term:
            // base = min_{k in [prev..l-1]} ( dp[k-1] - (psa[l-1] - psa[k-1]) )
            ll base = INF;
            for (int k = prev; k <= l-1; ++k) {
                base = min(base, dp[k-1] - (psa[l-1] - psa[k-1]));
            }
            // then for each i in [l, r), extra = base + dt[l-1].first * (i - l + 1)
            ll cost = 0; // incremental cost of pairing current chunk elements to dt[l-1].first
            for (int i = l; i < r; ++i) {
                cost += dt[i].first - dt[l-1].first; // add distance from dt[i] to dt[l-1]
                ll extra = base + dt[l-1].first * (i - l + 1);
                dp[i] = min(dp[i], cost + extra);
            }
        }

        prev = l;
        l = r;
    }

    // optional: debug print dp values
    for (int i = 1; i <= N_global; ++i) {
    }
    return dp[N_global];
}

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