Submission #1006139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006139		thangdz2k7	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	2396 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] += 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 * i - 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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45