Submission #67908

#	Time	Username	Problem	Language	Result	Execution time	Memory
67908		aquablitz11	Wiring (IOI17_wiring)	C++14	100 / 100	136 ms	18084 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
using pii = pair<int, int>;
using ll = long long;

const int N = 200010;
const int INF = 2e9+2;
int sz[N];
ll dp[N], qsl[N], qsr[N];

ll min_total_length(vector<int> R, vector<int> B)
{
    vector<pii> all;
    for (auto x : R) all.emplace_back(x, 0);
    for (auto x : B) all.emplace_back(x, 1);
    int n = all.size();
    all.emplace_back(-1, -1);
    sort(all.begin(), all.end());
    R.insert(R.begin(), -INF);
    R.insert(R.end(), INF);
    B.insert(B.begin(), -INF);
    B.insert(B.end(), INF);

    int z = 0;
    for (int i = 1; i <= n; ++i) {
        if (all[i].second != all[i-1].second) z = 0;
        sz[i] = ++z;
    }

    for (int i = 1; i <= n; ++i)
        qsl[i] = qsl[i-1] + all[i].first;
    for (int i = n; i >= 1; --i)
        qsr[i] = qsr[i+1] + (INF-all[i].first);

    for (int i = 1; i <= n; ++i) {
        ll nl, nr; // nearest opposite color of all[i].second to the left and to the right
        if (all[i].second == 0) {
            nl = *(lower_bound(B.begin(), B.end(), all[i].first)-1);
            nr = *lower_bound(B.begin(), B.end(), all[i].first);
        } else {
            nl = *(lower_bound(R.begin(), R.end(), all[i].first)-1);
            nr = *lower_bound(R.begin(), R.end(), all[i].first);
        }
        dp[i] = dp[i-1]+min(all[i].first-nl, nr-all[i].first);
        ll j = -1; // from j to i there will be one color followed by another color with equal amount
        if (sz[i-sz[i]] >= sz[i]) j = i-sz[i]-sz[i]+1;
        if (j != -1) {
            ll ml = (i+j)/2;
            ll mr = (i+j+1)/2;
            ll c = i-ml;
            ll cl = (all[ml].first*1ll*c) - (qsl[ml]-qsl[j-1]);
            ll cr = (INF-all[mr].first)*1ll*c - (qsr[mr]-qsr[i+1]);
            ll cm = (all[mr].first-all[ml].first)*c;
            dp[i] = min(dp[i], cl+cr+cm+dp[j-1]);
        }
    }
    return dp[n];
}

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