Submission #891928

#	Time	Username	Problem	Language	Result	Execution time	Memory
891928		vjudge1	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	348 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;

template<class T>
struct bivec {
    vector<T> neg, poz;
    bivec(int sz) : neg(sz, 0), poz(sz, 0) {}
    T &operator[](int p) {
        if(p >= 0) return poz[p];
        return neg[-p - 1];
    }
};

ll min_total_length(vi r, vi b) {
    int n = r.size(), m = b.size();
    vector<ii> V;
    for(auto it : r)
        V.push_back({it, 1});
    for(auto it : b)
        V.push_back({it, -1});
    sort(V.begin(), V.end());
    bivec<ll> dp(n + m);
    const ll INF = 1e18;
    for(int i = 1; i < n + m; ++i)
        dp[i] = dp[-i] = INF;
    dp[0] = 0;
    int ult = -1, len = n + m;
    for(auto [it, cul] : V) {
        if(ult != -1) {
            for(int i = -len; i < len; ++i) {
                dp[i] += abs(i) * (it - ult);
            }
        }
        ult = it;
        if(cul == 1) {
            for(int i = len - 1; i > -len; --i)
                dp[i] = dp[i - 1];
            for(int i = -len; i + 1 < len; ++i)
                dp[i + 1] = min(dp[i + 1], dp[i]);
        } else {
            for(int i = -len; i + 1 < len; ++i)
                dp[i] = dp[i + 1];
            for(int i = len - 1; i > -len; --i)
                dp[i - 1] = min(dp[i - 1], dp[i]);
        }
//        for(int i = -len; i < len; ++i)
//            cout << dp[i] << " ";
//        cout << "\n";
    }
    return dp[0];
}

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