Submission #1218086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218086		shmax	Wiring (IOI17_wiring)	C++20	30 / 100	1098 ms	15020 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);
}

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);
    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;
            for (int k = 0; k < prev.size() - (i == 1); 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;
    }
    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