제출 #1218129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218129		shmax	전선 연결 (IOI17_wiring)	C++20	30 / 100	1096 ms	42512 KiB

wiring

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

using namespace std;
using i32 = int32_t;
#define int long long
#define inf 1000'000'000'000'000'000LL
template<typename T>
using vec = vector<T>;

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}


template<typename it>
struct SparseTable {

    using T = typename remove_reference<decltype(*declval<it>())>::type;
    vector<vector<T>> t;
    function<T(T, T)> f;
    vector<int> log;

    SparseTable() = default;

    SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
        int n = distance(first, last);
        t.assign(32 - __builtin_clz(n), vector<T>(n));
        t[0].assign(first, last);
        //       calc log
        log.resize(n + 1);
        for (int i = 2; i <= n; i++)
            log[i] = log[i / 2] + 1;

        for (int i = 1; i < t.size(); i++)
            for (int j = 0; j < n - (1 << i) + 1; j++)
                t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
    }

    // returns f(a[l..r]) in O(1) time
    T get(int l, int r) {
        int h = log[r - l + 1];
        return f(t[h][l], t[h][r - (1 << h) + 1]);
    }
};

long long min_total_length(std::vector<i32> r, std::vector<i32> b) {
    vec<pair<int, int>> points;
    vec<vec<int>> cords(2, vec<int>());
    for (int i: r) {
        points.emplace_back(i, 0);
        cords[0].emplace_back(i);
    }
    for (int i: b) {
        points.emplace_back(i, 1);
        cords[1].emplace_back(i);
    }
    sort(cords[0].begin(), cords[0].end());
    sort(cords[1].begin(), cords[1].end());
    sort(points.begin(), points.end());
    int n = points.size();
    vec<vec<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || points[i].second != points[i - 1].second) {
            groups.emplace_back();
        }
        groups.back().emplace_back(points[i].first);
    }
    int m = groups.size();
    vec<vec<int>> dp(m);
    vec<pair<int, int>> prev;
    prev = {{0, groups[0].size()}};
    for (int t: groups[0]) {
        prev[0].first += groups[0].back() - t;
    }
    prev.emplace_back(inf, inf);

    SparseTable stmin(prev.begin(), prev.end(),
                      [](const pair<int, int> &a, const pair<int, int> &b) {
                          return a.first < b.first ? a : b;
                      });

    for (int i = 1; i < m; i++) {
        dp[i].resize(groups[i].size() + 1, inf);
        int d = groups[i].front() - groups[i - 1].back();
        int T = 0;
        {
            chmin(dp[i][0], prev.back().first);
        }
        for (int j = 1; j < dp[i].size(); j++) {
            T += groups[i][j - 1] - groups[i][0];

            dp[i][j] = inf;

            if (i == 1) {
                for (int k = 0; k < prev.size() - 1; k++) {
                    int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
                    chmin(dp[i][j], cost);
                }
                continue;
            }

//            var1
            {
                int L = max((int) prev.size() - j, 0LL);
                int R = prev.size() - 1;
//                for (int k = L; k <= R; k++) {
//                    int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
//                    chmin(dp[i][j], cost);
//                }
////
                if (L <= R)
                    dp[i][j] = stmin.get(L, R).first + T + d * j;
            }

            for (int k = 0; k < max((int) prev.size() - j, 0LL); k++) {
                int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
                chmin(dp[i][j], cost);
            }
        }
        vec<pair<int, int>> new_prev;
        new_prev.emplace_back(dp[i].back(), 0);
        int P = 0;
        for (int j = dp[i].size() - 2; j >= 0; j--) {
            P += groups[i].back() - groups[i][j];
            new_prev.emplace_back(dp[i][j] + P, dp[i].size() - j - 1);
        }
        reverse(new_prev.begin(), new_prev.end());


        prev = new_prev;
        stmin = SparseTable(prev.begin(), prev.end(),
                            [](const pair<int, int> &a, const pair<int, int> &b) {
                                return a.first < b.first ? a : b;
                            });

    }
    return dp[m - 1].back();
}

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