Submission #733139

#	Time	Username	Problem	Language	Result	Execution time	Memory
733139		t6twotwo	Wiring (IOI17_wiring)	C++17	17 / 100	1089 ms	12348 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct segment_tree {
    int n;
    vector<T> s;
    T (*f)(T, T);
    T e;
    segment_tree(int _n, T(*_f)(T, T), T _e) : f(_f), e(_e) {
        n = 2 << __lg(_n);
        s.resize(2 * n - 1, e);
    }
    void modify(int p, int l, int r, int x, T v) {
        if (r - l == 1) {
            s[p] = v;
            return;
        }
        int m = (l + r + 1) / 2;
        if (x < m) {
            modify(p * 2 + 1, l, m, x, v);
        } else {
            modify(p * 2 + 2, m, r, x, v);
        }
        s[p] = f(s[p * 2 + 1], s[p * 2 + 2]);
    }
    void modify(int x, T v) {
        modify(0, 0, n, x, v);
    }
    T range_query(int p, int l, int r, int L, int R) {
        if (R <= l || r <= L) {
            return e;
        }
        if (L <= l && r <= R) {
            return s[p];
        }
        int m = (l + r + 1) / 2;
        return f(range_query(p * 2 + 1, l, m, L, R), range_query(p * 2 + 2, m, r, L, R));
    }
    T range_query(int l, int r) {
        return range_query(0, 0, n, l, r);
    }
};
ll fmin(ll x, ll y) {
    return min(x, y);
}
constexpr ll inf = 1E16;
long long min_total_length(vector<int> R, vector<int> B) {
    int N = R.size();
    int M = B.size();
    vector<array<int, 2>> T;
    for (int x : R) {
        T.push_back({x, 0});
    }
    for (int x : B) {
        T.push_back({x, 1});
    }
    sort(T.begin(), T.end());
    vector<ll> pfs(N + M + 1);
    for (int i = 0; i < N + M; i++) {
        pfs[i + 1] = pfs[i] + T[i][0];
    }
    vector<int> e(N + M, -1);
    for (int i = N + M - 2; i >= 0; i--) {
        if (T[i][1] == T[i + 1][1]) {
            e[i] = e[i + 1];
        } else {
            e[i] = i + 1;
        }
    }
    vector<int> d(N + M, -1);
    segment_tree<ll> st(N + M, fmin, inf);
    vector<ll> dp(N + M + 1, inf);
    dp[0] = 0;
    for (int i = 0; i < N + M; i++) {
        if (i > 0) {
            if (T[i][1] == T[i - 1][1]) {
                d[i] = d[i - 1];
            } else {
                d[i] = i - 1;
            }
        }
        if (d[i] == -1) {
            continue;
        }
        int j = d[i];
        dp[i + 1] = min(dp[i + 1], dp[j + 1] + (pfs[i + 1] - pfs[j + 1]) - 1LL * (i - j) * T[j][0]);
        for (int p = d[j] + 1; p <= j; p++) {
            int m = min(j - p + 1, i - j);
            ll s = 0;
            if (j + 1 - p >= i - j) {
                s = (pfs[p] - 1LL * p * T[j + 1][0]) + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j + 1][0]);
            } else {
                s = (pfs[p] - 1LL * p * T[j][0]) + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j][0]);
            }
            dp[i + 1] = min(dp[i + 1], dp[p] + s);
        }
    }
    return dp[N + M];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:90:17: warning: unused variable 'm' [-Wunused-variable]
   90 |             int m = min(j - p + 1, i - j);
      |                 ^

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