제출 #574245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574245		KoD	Wiring (IOI17_wiring)	C++17	0 / 100	1085 ms	5068 KiB

wiring

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

using ll = long long;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

ll min_total_length(vector<int> A, vector<int> B) {
    int ai = 0, bi = 0;
    vector<int> left;
    vector<ll> dp;
    while (ai < (int)A.size() or bi < (int)B.size()) {
        if (ai == (int)A.size() or (bi < (int)B.size() and A[ai] > B[bi])) {
            std::swap(A, B);
            std::swap(ai, bi);
        }
        vector<int> right;
        while (ai < (int)A.size() and (bi == (int)B.size() or A[ai] < B[bi])) {
            right.push_back(A[ai]);
            ai += 1;
        }
        const int lsz = (int)left.size();
        const int rsz = (int)right.size();
        if (lsz == 0) {
            left = std::move(right);
            dp.resize(rsz + 1, infty<ll>);
            dp[rsz] = 0;
            continue;
        }
        vector<ll> lsum(lsz + 1);
        for (int i = 0; i < lsz; ++i) {
            lsum[i + 1] = lsum[i] + (left[lsz - 1] - left[lsz - i - 1]);
        }
        vector<ll> rsum(rsz + 1);
        for (int i = 0; i < rsz; ++i) {
            rsum[i + 1] = rsum[i] + (right[i] - right[0]);
        }
        const ll between = right[0] - left[lsz - 1];
        // vector<ll> pre1(lsz + 1), pre2(lsz + 1);
        // for (int l = 1; l <= lsz; ++l) {
        //     pre1[l] = dp[l] + lsum[l];
        //     pre2[l] = dp[l] + lsum[l] + between * l;
        // }
        // for (int l = 2; l <= lsz; ++l) {
        //     pre1[l] = std::min(pre1[l], pre1[l - 1]);
        // }
        // for (int l = lsz - 1; l >= 1; --l) {
        //     pre2[l] = std::min(pre2[l], pre2[l + 1]);
        // }
        vector<ll> next(rsz + 1);
        next[0] = dp[0];
        for (int r = 1; r <= rsz; ++r) {
            // 1 <= l <= r : dp[l] + lsum[l] + rsum[r] + between * r 
            // r <= l      : dp[l] + lsum[l] + rsum[r] + between * l
            // if (r <= lsz) {
            //     next[r] = std::min(pre1[r] + rsum[r] + between * r, pre2[r] + rsum[r]);
            // } else {
            //     next[r] = pre1[lsz] + rsum[r] + between * r;
            // }
            next[r] = infty<ll>;
            for (int l = 1; l <= lsz; ++l) {
                next[r] = std::min(next[r], dp[l] + lsum[l] + rsum[r] + std::max(l, r) * between);
            }
        }
        left = std::move(right);
        dp.resize(rsz + 1);
        for (int i = 0; i <= rsz; ++i) {
            dp[rsz - i] = next[i];
        }
    }
    return dp[0];
}

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