Submission #733332

#	Time	Username	Problem	Language	Result	Execution time	Memory
733332		t6twotwo	Wiring (IOI17_wiring)	C++17	100 / 100	40 ms	7068 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1E16;
long long min_total_length(vector<int> R, vector<int> B) {
    int N = R.size();
    int M = B.size();
    vector<array<int, 2>> T;
    for (int i = 0, j = 0; i < N || j < M;) {
        if (i < N && (j == M || R[i] < B[j])) {
            T.push_back({R[i++], 0});
        } else {
            T.push_back({B[j++], 1});
        }
    }
    vector<ll> dp(N + M + 1, inf);
    dp[0] = 0;
    for (int i = 0, j = 0, k = 0; j < N + M; i = j, j = k) {
        while (k < N + M && T[k][1] == T[j][1]) {
            k++;
        }
        for (int p = i; p < j; p++) {
            dp[p + 1] = min(dp[p + 1], dp[p] + T[j][0] - T[p][0]);
        }
        ll s = 0;
        for (int p = 0; j + p < k && j - 1 - p >= i; p++) {
            s += T[j + p][0] - T[j - 1 - p][0];
            dp[j + p + 1] = min(dp[j + p + 1], dp[j - 1 - p] + s);
        }
        if (j > 0) {
            for (int p = j; p < k; p++) {
                dp[p + 1] = min(dp[p + 1], dp[p] + T[p][0] - T[j - 1][0]);
            }
        }
    }
    return dp[N + M];
}

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