Submission #422300

#	Time	Username	Problem	Language	Result	Execution time	Memory
422300		timmyfeng	Wiring (IOI17_wiring)	C++17	100 / 100	60 ms	8072 KiB

wiring

#include <bits/stdc++.h>
using namespace std;

const long long L = 1000000000000000LL;

long long min_total_length(vector<int> r, vector<int> b) {
    vector<array<int, 2>> points;
    for (auto i : r) {
        points.push_back({i, 0});
    }
    for (auto i : b) {
        points.push_back({i, 1});
    }
    sort(points.begin(), points.end());

    vector<long long> cost;
    for (int i = 0, j = 0; i < (int) points.size(); i = j) {
        while (j < (int) points.size() && points[j][1] == points[i][1]) {
            ++j;
        }

        if (i == 0) {
            cost.resize(j + 1);
            for (int k = 0; k < j; ++k) {
                cost[j] += points[j - 1][0] - points[k][0];
                cost[k] = L;
            }
        } else {
            long long gap = points[i][0] - points[i - 1][0];

            vector<long long> prefix = cost;
            for (int k = 1; k < (int) cost.size(); ++k) {
                prefix[k] = min(prefix[k], prefix[k - 1]);
            }

            vector<long long> suffix = cost;
            for (int k = cost.size() - 1; k >= 0; --k) {
                suffix[k] += k * gap;
                if (k < (int) cost.size() - 1) {
                    suffix[k] = min(suffix[k], suffix[k + 1]);
                }
            }

            long long sum = 0;
            cost.resize(j - i + 1);
            for (int k = 0; k <= j - i; ++k) {
                sum += k > 0 ? points[i + k - 1][0] - points[i][0] : 0;
                if (k < (int) prefix.size()) {
                    cost[k] = sum + min(suffix[k], prefix[k] + k * gap);
                } else {
                    cost[k] = sum + prefix.back() + k * gap;
                }
            }

            sum = 0;
            for (int k = j - i - 1; k >= 0; --k) {
                sum += points[j - 1][0] - points[i + k][0];
                cost[k] += sum;
            }

            reverse(cost.begin(), cost.end());
        }
    }

    return cost[0];
}

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