Submission #268772

#	Time	Username	Problem	Language	Result	Execution time	Memory
268772		hamerin	Wiring (IOI17_wiring)	C++17	7 / 100	255 ms	262148 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<vector<i64>> dp(R + 1, vector<i64>(B + 1));
	for(int i=1;i<=R;i++) dp[i][0] = inf;
	for(int i=1;i<=B;i++) dp[0][i] = inf;

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= B; j++) {
            auto it1 = lower_bound(iterall(Bv), Rv[i]);
            auto it2 = lower_bound(iterall(Rv), Bv[j]);

            i64 dR = min(*it1 - Rv[i], Rv[i] - *prev(it1));
            i64 dB = min(*it2 - Bv[j], Bv[j] - *prev(it2));

            dp[i][j] = min({dp[i - 1][j] + dR, dp[i][j - 1] + dB,
                            dp[i - 1][j - 1] + abs(Rv[i] - Bv[j])});
        }
    }

    return dp[R][B];
}

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