제출 #643354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643354		piOOE	전선 연결 (IOI17_wiring)	C++17	100 / 100	26 ms	6860 KiB

wiring

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

using namespace std;
using ll = long long;

constexpr ll inf = 2.28e18;

ll min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size(), m = b.size();

    vector<int> x(n + m), tp(n + m);

    int pnt_r = 0, pnt_b = 0, pnt = 0;
    while (pnt_r < n || pnt_b < m) {
        if (pnt_r < n && (pnt_b == m || r[pnt_r] <= b[pnt_b])) {
            x[pnt++] = r[pnt_r++];
        } else {
            x[pnt] = b[pnt_b++];
            tp[pnt++] = 1;
        }
    }

    n += m;

    vector<ll> dp(n + 1, inf);
    dp[0] = 0;
    for (int i = 0, j, p = 0; i < n; p = i, i = j) {
        j = i + 1;
        while (j < n && tp[j] == tp[i]) {
            ++j;
        }

        if (i > 0) {
            for (int k = p; k < i; ++k) {
                dp[k + 1] = min(dp[k + 1], dp[k] + x[i] - x[k]);
            }

            ll sum = 0;
            for (int k = i; k < j && i - (k - i) - 1 >= p; ++k) {
                sum += x[k] - x[i - (k - i) - 1];
                dp[k + 1] = min(dp[k + 1], dp[i - (k - i) - 1] + sum);
            }

            for (int k = i; k < j; ++k) {
                dp[k + 1] = min(dp[k + 1], dp[k] + x[k] - x[i - 1]);
            }
        }
    }

    return dp[n];
}

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