Submission #133506

#	Time	Username	Problem	Language	Result	Execution time	Memory
133506		Osama_Alkhodairy	Wiring (IOI17_wiring)	C++17	100 / 100	157 ms	20384 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    vector <pair <int, int> > a;
    set <int> g, h;
    for(auto &i : r){
        a.push_back(make_pair(i, -1));
        g.insert(i);
    }
    for(auto &i : b){
        a.push_back(make_pair(i, 1));
        h.insert(i);
    }
    sort(a.begin(), a.end());
    int n = a.size();
    a.insert(a.begin(), make_pair(-1, -1));
    vector <int> w(n + 1, -1), p(2 * n + 1, -1);
    vector <ll> sum(n + 1);
    int cur = n;
    p[n] = 0;
    for(int i = 1 ; i <= n ; i++){
        sum[i] = sum[i - 1] + a[i].first * a[i].second;
        cur += a[i].second;
        if(p[cur] != -1) w[i] = p[cur];
        p[cur] = i;
    }
    auto near = [&](int i){
        set <int> &s = (a[i].second == -1 ? h : g);
        int ret = 1e9;
        int x = a[i].first;
        auto it = s.lower_bound(x);
        if(it != s.end()) ret = min(ret, *it - x);
        if(it != s.begin()) ret = min(ret, x - *(--it));
        return ret;
    };
    vector <ll> dp(n + 1);
    for(int i = 1 ; i <= n ; i++){
        dp[i] = dp[i - 1] + near(i);
        if(w[i] != -1) dp[i] = min(dp[i], dp[w[i]] + abs(sum[i] - sum[w[i]]));
    }
    return dp[n];
}

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