Submission #589563

#	Time	Username	Problem	Language	Result	Execution time	Memory
589563		TheScrasse	Wiring (IOI17_wiring)	C++17	0 / 100	2 ms	3412 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 200010

long long min_total_length(vector<int> _r, vector<int> _b) {
    ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
    ll c1, c2, dp[maxn], bsl, bsm, bsu, ps[maxn];
    vector<array<ll, 2>> v;

    n = _r.size(); m = _b.size(); v.pb({-1, -1});
    for (i = 1; i <= n; i++) a[i] = _r[i - 1], v.pb({a[i], 0});
    for (i = 1; i <= m; i++) b[i] = _b[i - 1], v.pb({b[i], 1});

    sort(v.begin(), v.end());

    dp[0] = 0; dp[1] = 0;
    for (i = 2; i <= n + m; i++) dp[i] = INF, ps[i] = ps[i - 1] + v[i][0];

    auto rs = [&](ll l, ll r) {
        return (ps[r] - ps[l - 1]);
    };

    auto calc = [&](ll bsm) {
        ll l1, r1, l2, r2, rr;
        l1 = bsm; r1 = c1 - 1; l2 = c1; r2 = i; rr = dp[bsm - 1];

        // cout << "calc" _ l1 _ r1 _ l2 _ r2 << nl;

        if (l1 > r1 || l2 > r2) return INF;
        rr -= rs(l1, r1); rr += rs(l2, r2);
        if (r1 - l1 > r2 - l2) rr += (((r1 - l1) - (r2 - l2)) * rs(l2, l2));
        else rr += (((r1 - l1) - (r2 - l2)) * rs(r1, r1));

        // cout << "rr =" _ rr << nl;
        return rr;
    };

    auto good = [&](ll bsm) {
        return (calc(bsm) <= calc(bsm + 1));
    };

    c1 = 1; c2 = -1;
    for (i = 2; i <= n + m; i++) {
        if (v[i][1] != v[i - 1][1]) c2 = c1, c1 = i;
        if (c2 == -1) {
            dp[i] = 0; continue;
        }

        bsl = c2 - 1; bsu = c1;
        // cout << "i, bsl, bsu =" _ i _ bsl _ bsu << nl;
        while (bsl != bsu) {
            bsm = (bsl + bsu) / 2;
            if (good(bsm)) bsu = bsm;
            else bsl = bsm + 1;
        }

        dp[i] = calc(bsl);
        // cout << "dp =" _ bsl _ dp[i] << nl;
    }

    /* for (i = 1; i <= n + m; i++) cout << dp[i] << ' ';
    cout << nl; */

	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:16:11: warning: unused variable 'i1' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |           ^~
wiring.cpp:16:15: warning: unused variable 'j' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |               ^
wiring.cpp:16:18: warning: unused variable 'k' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                  ^
wiring.cpp:16:21: warning: unused variable 'k1' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                     ^~
wiring.cpp:16:25: warning: unused variable 't' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                         ^
wiring.cpp:16:34: warning: unused variable 'res' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                                  ^~~
wiring.cpp:16:39: warning: unused variable 'flag' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                                       ^~~~

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