제출 #891933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891933		vjudge1	전선 연결 (IOI17_wiring)	C++17	7 / 100	1050 ms	8640 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, T v0) : neg(sz, v0), poz(sz, v0) {}
    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());
    const ll INF = 1e18;
    bivec<ll> dp(n + m + 5, 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; i > -len; --i)
                dp[i] = dp[i - 1];
            dp[-len] = INF;
            for(int i = -len; i < len; ++i)
                dp[i + 1] = min(dp[i + 1], dp[i]);
        } else {
            for(int i = -len; i < len; ++i)
                dp[i] = dp[i + 1];
            dp[len] = INF;
            for(int i = len; 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: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45