Submission #747004

#	Time	Username	Problem	Language	Result	Execution time	Memory
747004		danikoynov	Wiring (IOI17_wiring)	C++14	100 / 100	67 ms	32428 KiB

wiring

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

const int maxn = 2e5 + 10;

const ll inf = 1e18;
int n, m;
ll r[maxn], b[maxn], x[maxn], t[maxn];
int sz, cp_sz[maxn];
vector < ll > st[maxn], pref[maxn];
vector < ll > dp[maxn];
ll get_range(int row, int l, int r)
{
    if (r < l)
        return 0;
    if (l == 0)
        return pref[row][r];

    return pref[row][r] - pref[row][l - 1];
}
ll min_total_length(vector<int> R, vector<int> B)
{
    n = R.size();
    m = B.size();
    vector < pair < int, int > > vec;
    for (int i = 1; i <= n; i ++)
        r[i] = R[i - 1], vec.push_back({r[i], 0});
    for (int i = 1; i <= m; i ++)
        b[i] = B[i - 1], vec.push_back({b[i], 1});

    sort(vec.begin(), vec.end());
    for (int i = 1; i <= n + m; i ++)
    {
        x[i] = vec[i - 1].first;
        t[i] = vec[i - 1].second;
    }
    st[1].push_back(x[1]);
    cp_sz[1] ++;
    sz = 1;
    for (int i = 2; i <= n + m; i ++)
    {
        if (t[i] != t[i - 1])
            sz ++;
        cp_sz[sz] ++;
        st[sz].push_back(x[i]);
    }
    for (int i = 1; i <= sz; i++)
    {
        dp[i].resize(cp_sz[i] + 1, inf);
        pref[i].resize(cp_sz[i]);
        pref[i][0] = st[i][0];
        for (int j = 1; j < cp_sz[i]; j ++)
            pref[i][j] = pref[i][j - 1] + st[i][j];
    }
    dp[1][cp_sz[1]] = 0;

    for (int i = 2; i <= sz; i ++)
    {
        for (int tk = cp_sz[i - 1]; tk > 0; tk --)
        {
            dp[i - 1][tk - 1] = min(dp[i - 1][tk - 1], dp[i - 1][tk] + (st[i][0] - st[i - 1][cp_sz[i - 1] - tk]));
        }

        for (int tk = 0; tk <= min(cp_sz[i - 1], cp_sz[i]); tk ++)
        {
            dp[i][cp_sz[i] - tk] = min(dp[i][cp_sz[i] - tk], dp[i - 1][tk] +
                                       get_range(i, 0, tk - 1) - get_range(i - 1, cp_sz[i - 1] - tk, cp_sz[i - 1] - 1));
        }

        for (int tk = cp_sz[i]; tk > 0; tk --)
        {
            dp[i][tk - 1] = min(dp[i][tk - 1], dp[i][tk] + (st[i][cp_sz[i] - tk] - st[i - 1].back()));
        }
    }

    return dp[sz][0];
}

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