Submission #1203752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203752		onbert	Wiring (IOI17_wiring)	C++20	0 / 100	0 ms	328 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int min_total_length(vector<int32_t> a, vector<int32_t> b) {
    if (a.size() > b.size()) swap(a, b);
    int n = a.size(), m = b.size();
    vector<pair<int,int>> vec;
    for (int i:a) vec.push_back({i, -1});
    for (int i:b) vec.push_back({i, 1});
    sort(vec.begin(), vec.end());
    int sz = n+m;
    pair<int,int> dp[sz];
    for (int i=0;i<sz;i++) dp[i] = {INF, -INF};
    dp[0] = {0, 0};
    int lasta = -INF, lastb = -INF, last = 0, val = 0, sum = 0;
    int start = max(a[0], b[0]);
    for (auto [i, del]:vec) {
        val += del;
        sum += del * i;
        if (i < start) {
            last += start - i;
            continue;
        }
        int cur;
        if (start == i) {
            cur = last;
        } else if (del == 1) {
            cur = min(last + i - lasta, dp[val + n].first + abs(sum - dp[val + n].second));
            lastb = i;
        } else {
            cur = min(last + i - lastb, dp[val + n].first + abs(sum - dp[val + n].second));
            lasta = i;
        }
        dp[val + n] = {cur, sum};
        last = cur;
    }
    return last;
}

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