제출 #1006144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006144		thangdz2k7	전선 연결 (IOI17_wiring)	C++17	100 / 100	32 ms	8640 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int inf = 1e9;

int n;
long long dp[N], pre[N];
pair <int, int> p[N];

long long min_total_length(vector <int> r, vector <int> b){

    for (auto &i : r) p[++ n] = {i, 0};
    for (auto &i : b) p[++ n] = {i, 1};
    sort(p + 1, p + n + 1);
    p[0] = {-inf, 1 - p[1].second};

    for (int i = 1; i <= n; ++ i) pre[i] = pre[i - 1] + p[i].first;

    for (int last = 1, i = 1; i <= n; ++ i){
        int j = i;
        while (j < n && p[j].second == p[j + 1].second) ++ j;
        for (int k = last; k < i; ++ k) dp[k] = min(dp[k], dp[k - 1] + p[i].first - p[k].first);

        long long Min = dp[i - 1], sum = 0;
        for (int k = i; k <= j; ++ k){
            sum += p[k].first - p[i - 1].first;
            int vc = i * 2 - k - 1;
            if (vc >= last){
                Min = min(Min, dp[vc - 1] + 1ll * p[i - 1].first * (i - vc) - pre[i - 1] + pre[vc - 1]);
            }

            dp[k] = Min + sum;
        }

        last = i;
        i = j;
    }

    return dp[n];
}

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