Submission #56215

#	Time	Username	Problem	Language	Result	Execution time	Memory
56215		fallingstar	Wiring (IOI17_wiring)	C++14	100 / 100	96 ms	94848 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <vector>
#include <queue>

#define long long long

using namespace std;

typedef pair<int, int> pii;

const int N = 2e5 + 2;
const long INF = 1LL << 60;

int n;
long f[N], pref[N], suff[N];
pair<int, bool> a[N];

long Solve()
{
    sort(a + 1, a + 1 + n);
    int lastL = 0, lastR = 0, gap = 0;
    long rsum = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i > 1 && a[i].second != a[i - 1].second)
        {
            lastL = lastR + 1;
            lastR = i - 1;
            gap = a[i].first - a[i - 1].first;
            pref[lastL - 1] = suff[lastR + 1] = INF;
            long lsum = 0;
            for (int j = lastR; j >= lastL; --j)
            {
                lsum += a[lastR].first - a[j].first;
                suff[j] = min(suff[j + 1], min(f[j - 1], f[j]) + lsum);
                pref[j] = min(f[j - 1], f[j]) + lsum + (long) (lastR - j + 1) * gap;
            }
            for (int j = lastL + 1; j <= lastR; ++j)
                pref[j] = min(pref[j], pref[j - 1]);
            rsum = 0;
        }
        rsum += a[i].first - a[lastR + 1].first;
        f[i] = INF;
        if (lastR != 0)
        {
            f[i] = min(f[i], suff[max(lastR * 2 - i + 1, lastL)] + (long) (i - lastR) * gap + rsum);
            
            f[i] = min(f[i], pref[max(lastR * 2 - i + 1, lastL) - 1] + rsum);
        }
    }
    return f[n];
}

long min_total_length(vector<int> r_, vector<int> b_) {
    for (int p: r_) a[++n] = {p, 0};
    for (int p: b_) a[++n] = {p, 1};
	return Solve();
}

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