Submission #269290

#	Time	Username	Problem	Language	Result	Execution time	Memory
269290		hamerin	Wiring (IOI17_wiring)	C++17	0 / 100	107 ms	15008 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

int inf = numeric_limits<int>::max() / 2;

i64 min_total_length(vector<int> r, vector<int> b) {
    const int R = r.size();
    const int B = b.size();

    vector<int> Rv, Bv;
    Rv.emplace_back(-inf);
    Bv.emplace_back(-inf);
    copy(iterall(r), back_inserter(Rv));
    copy(iterall(b), back_inserter(Bv));
    Rv.emplace_back(inf);
    Bv.emplace_back(inf);

    vector<pair<int, bool>> seq;
    for (auto el : r) seq.emplace_back(el, true);
    for (auto el : b) seq.emplace_back(el, false);
    sort(iterall(seq), [](auto l, auto r) { return l.first < r.first; });

    int n = 1;
    vector<int> rhm(1), bhm(1);
    vector<i64> rs(1), bs(1);
    for (auto [el, clr] : seq) {
        if (clr)
            rhm.emplace_back(1);
        else
            rhm.emplace_back(0);

        if (!clr)
            bhm.emplace_back(1);
        else
            bhm.emplace_back(0);

        if (clr)
            rs.emplace_back(el);
        else
            rs.emplace_back(0);

        if (!clr)
            bs.emplace_back(el);
        else
            bs.emplace_back(0);

        rhm[n] += rhm[n - 1];
        bhm[n] += bhm[n - 1];
        rs[n] += rs[n - 1];
        bs[n] += bs[n - 1];
        ++n;
    }

    map<int, int> hmInterval;
    vector<i64> dp(R + B);

	hmInterval[0] = -1;
    for (int i = 0; i < R + B; i++) {
        auto [el, clr] = seq[i];

        i64 d;
        if (clr) {
            auto it = lower_bound(iterall(Bv), el);
            d = min(*it - el, el - *prev(it));
        } else {
            auto it = lower_bound(iterall(Rv), el);
            d = min(*it - el, el - *prev(it));
        }

        dp[i] = (i ? dp[i - 1] : 0) + d;

        auto it = hmInterval.find(rhm[i + 1] - bhm[i + 1]);
        if (it != hmInterval.end()) {
            auto j = it->second;
            dp[i] = min(dp[i], dp[j] + abs(rs[i + 1] - rs[j + 1] - bs[i + 1] +
                                           bs[j + 1]));
        }
        hmInterval[rhm[i + 1] - bhm[i + 1]] = i;
    }

    return dp.back();
}

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