Submission #733114

#	Time	Username	Problem	Language	Result	Execution time	Memory
733114		t6twotwo	Wiring (IOI17_wiring)	C++17	17 / 100	1077 ms	7036 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int64_t inf = 1E16;
long long min_total_length(vector<int> R, vector<int> B) {
    int N = R.size();
    int M = B.size();
    vector<array<int, 2>> T;
    for (int x : R) {
        T.push_back({x, 0});
    }
    for (int x : B) {
        T.push_back({x, 1});
    }
    sort(T.begin(), T.end());
    vector<int64_t> dp(N + M + 1, inf);
    dp[0] = 0;
    for (int i = 0; i < N + M; i++) {
        int j = i - 1;
        while (j >= 0 && T[j][1] == T[i][1]) {
            j--;
        }
        if (j >= 0) {
            int64_t s = 0;
            for (int p = j + 1; p <= i; p++) {
                s += T[p][0] - T[j][0];
            }
            dp[i + 1] = min(dp[i + 1], dp[j + 1] + s);
        }
        int k = j + 1;
        while (j >= 0 && T[j][1] != T[i][1]) {
            int64_t s = 0;
            int m = min(k - j, i - k + 1);
            for (int p = 0; p < m; p++) {
                s += T[i - p][0] - T[j + p][0];
            }
            for (int p = j + m; p < k; p++) {
                s += T[k][0] - T[p][0];
            }
            for (int p = k; p <= i - m; p++) {
                s += T[p][0] - T[k - 1][0];
            }
            dp[i + 1] = min(dp[i + 1], dp[j] + s);
            j--;
        }
    }
    return dp[N + M];
}

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