제출 #1146453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146453		MtSaka	전선 연결 (IOI17_wiring)	C++20	100 / 100	68 ms	6676 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define overload(a, b, c, d, ...) d
#define rep1(n) for (ll _ = 0; _ < (ll)(n); ++_)
#define rep2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep3(i, l, r) for (ll i = (ll)(l); i < (ll)(r); ++i)
#define rep(...) overload(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define rrep2(i, l, r) for (ll i = (ll)(r) - 1; i >= (ll)(l); --i)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;
using ull = unsigned long long;
using pl = pair<ll, ll>;
using vp = vector<pl>;
template <typename T, typename U>
inline constexpr bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
template <typename T, typename U>
inline constexpr bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        os << *it;
        if (it != prev(v.end())) os << ' ';
    }
    return os;
}
template <typename T>
void print(const T& a) { cout << a << '\n'; }
template <typename Head, typename... Tail>
void print(const Head& a, const Tail&... b) {
    cout << a << ' ';
    print(b...);
}
template <typename T>
void dbg(const T& a) {
#ifndef EVAL
    cerr << a << '\n';
#endif
}
template <typename Head, typename... Tail>
void dbg(const Head& a, const Tail&... b) {
#ifndef EVAL
    cout << a << ' ';
    print(b...);
#endif
}
static constexpr ll inf = numeric_limits<ll>::max() / 2;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size(), m = b.size();
    vp p;
    rep(i, n) p.eb(r[i], 0);
    rep(i, m) p.eb(b[i], 1);
    sort(all(p));
    auto get = [&](ll a, ll x) -> ll {
        ll res = inf;
        if (x == 0) {
            auto it = lower_bound(all(b), a);
            if (it != b.end()) chmin(res, *it - a);
            if (it != b.begin()) chmin(res, a - *prev(it));
        } else {
            auto it = lower_bound(all(r), a);
            if (it != r.end()) chmin(res, *it - a);
            if (it != r.begin()) chmin(res, a - *prev(it));
        }
        return res;
    };
    vl dp(n + m + 1, inf);
    dp[0] = 0;
    ll sum = 0, idx = -1;
    rep(i, n + m) {
        chmin(dp[i + 1], dp[i] + get(p[i].first, p[i].second));
        if (i > 0 && p[i - 1].second != p[i].second) {
            idx = i - 1;
            sum = p[i].first - p[i - 1].first;
        } else if (idx > 0 && p[idx].second == p[idx - 1].second) {
            sum += p[i].first - p[idx - 1].first;
            idx--;
        } else
            idx = -1;
        if (idx != -1) chmin(dp[i + 1], dp[idx] + sum);
    }
    // dbg(dp);
    return dp[n + m];
}

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