Submission #98432

#	Time	Username	Problem	Language	Result	Execution time	Memory
98432		bogdan10bos	Wiring (IOI17_wiring)	C++14	100 / 100	177 ms	13080 KiB

wiring

#include <bits/stdc++.h>

#include "wiring.h"

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

LL min_total_length(vector<int> r, vector<int> b)
{
    int N = r.size(), M = b.size();
    int K = N + M;

	vector<pii> v;
	for(auto &x: r) v.emplace_back(x, 0);
	for(auto &x: b) v.emplace_back(x, 1);
	sort(begin(v), end(v));

	vector<LL> sum;
	sum.resize(K + 5);
	sum[0] = v[0].first;
	for(int i = 1; i < K; i++)  sum[i] = sum[i - 1] + v[i].first;

	vector<LL> dp;
	dp.resize(K + 5);

    multiset<LL> lessK, moreK;

	int st = -1, lstst = -1, lstdr = -1, col = -1;
	for(int i = 0; i < K; i++)
    {
        if(col != v[i].second)
        {
            lstst = st, lstdr = i - 1;
            st = i, col = v[i].second;
            lessK.clear(), moreK.clear();

            if(lstst != -1)
            {
                LL cost = 0LL;
                for(int i = lstdr; i >= lstst; i--)
                {
                    cost += v[st].first - v[i].first;
                    LL dpcost = cost;
                    if(i > 0)   dpcost += dp[i - 1];
                    lessK.insert(dpcost);
                }
                moreK.insert(dp[lstdr]);
            }
        }

        dp[i] = 1LL << 60;
        if(lstst == -1) continue;

        LL sumRight = (sum[i] - sum[st]) - 1LL * (i - st) * v[st].first;
        int lgt = (i - st + 1);

        if(!lessK.empty())
        {
            LL cost = sumRight + (*lessK.begin());
            dp[i] = min(dp[i], cost);
        }
        if(!moreK.empty())
        {
            LL cost = sumRight + 1LL * lgt * (v[st].first - v[lstdr].first) + (*moreK.begin());
            dp[i] = min(dp[i], cost);
        }

        if(lstdr - lstst + 1 >= lgt)
        {
            LL sumLeft = 1LL * lgt * v[lstdr].first - (sum[lstdr] - sum[lstdr - lgt + 1] + v[lstdr - lgt + 1].first);
            LL cost = sumLeft;
            if(lstdr - lgt + 1 > 0) cost += dp[lstdr - lgt];
            moreK.insert(cost);
            cost += 1LL * lgt * (v[st].first - v[lstdr].first);
            lessK.erase( lessK.find(cost) );
        }
    }

    return dp[K - 1];
}

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