제출 #1141612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141612		anmattroi	전선 연결 (IOI17_wiring)	C++17	100 / 100	43 ms	11044 KiB

wiring

/********************************************

Task: IOI17_WIRING
Link: https://oj.uz/problem/view/IOI17_wiring

********************************************/

#include <bits/stdc++.h>
#include "wiring.h"
#define fi first
#define se second
#define maxn 100005
using namespace std;
using ii = pair<int, int>;

template <class T> inline constexpr void cmin(T &x, const T &y) {if (x > y) x = y;}

int n, m, N;

ii a[2*maxn];
vector<vector<int> > v;
vector<vector<int64_t> > s;

int64_t dp[2][2*maxn];

int64_t solve() {
    N = n+m;
    sort(a, a + N);

    for (int i2 = 0; i2 < N;) {
        int i1 = i2;
        vector<int> p(1, 0);
        while (i2 < N && a[i2].se == a[i1].se) ++i2;
        for (int i = i1; i < i2; i++) p.emplace_back(a[i].fi);
        vector<int64_t> prefix_sum(int(p.size()), 0);
        for (int i = 1; i < p.size(); i++) prefix_sum[i] = prefix_sum[i-1] + p[i];
        v.emplace_back(p);
        s.emplace_back(prefix_sum);
    }


    int sz = v.size();
    dp[0][0] = 0;
    for (int i = 1; i < v[0].size(); i++) dp[0][i] = LLONG_MAX/100;

    for (int o = 1; o < sz; o++) {
        int L = v[o-1].size()-1, R = v[o].size()-1,
        u1 = (o&1), u2 = 1-u1;

        int LIM = max(L, R);
        vector<int64_t> prefix_sum = s[o-1];
        vector<int64_t> prefix_min(LIM+2, LLONG_MAX/100), suffix_min(LIM+2, LLONG_MAX/100);
        //suffix when L > R --> L-R must be connected to the first one of R
        //prefix when L <= R --> R-L must be connected to the last one of L

        for (int i = 0; i <= L; i++) {
            int rr = L-i;
            cmin(suffix_min[rr], dp[u2][i] + prefix_sum[i] - prefix_sum[L] + int64_t(rr) * v[o][1]);
            cmin(prefix_min[rr], dp[u2][i] + prefix_sum[i] - prefix_sum[L] + int64_t(rr) * v[o-1][L]);
        }
        for (int i = 1; i <= LIM; i++) cmin(prefix_min[i], prefix_min[i-1]);
        for (int i = LIM; i >= 0; i--) cmin(suffix_min[i], suffix_min[i+1]);

        prefix_sum = s[o];

        dp[u1][0] = dp[u2][L];
        for (int i = 1; i <= R; i++) dp[u1][i] = min(prefix_sum[i] + suffix_min[i] - int64_t(i) * v[o][1],
                                                     prefix_sum[i] + prefix_min[i] - int64_t(i) * v[o-1][L]);
    }

    return dp[(sz-1)&1][v[sz-1].size()-1];

}
/*
4 5
1 2 3 7
0 4 5 9 10

10
*/

long long min_total_length(vector<int> r, vector<int> b) {
    n = r.size(); m = b.size();
    for (int i = 0; i < n; i++) a[i] = {r[i], 0};
    for (int i = 0; i < m; i++) a[i+n] = {b[i], 1};

	return solve();
}

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