Submission #407384

#	Time	Username	Problem	Language	Result	Execution time	Memory
407384		Peti	Wiring (IOI17_wiring)	C++14	100 / 100	64 ms	8608 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

long long INF = (long long)1e10;

vector<pair<int, int>> v;
vector<long long> ossz, dp;

long long ertek(int l, int m, int r){
    long long ossz1 = ossz[m-1]-ossz[l-1], ossz2 = ossz[r]-ossz[m-1];
    if(m-l < r-m+1)
        ossz1 += (long long)v[m-1].first*(r-2*m+l+1);
    else
        ossz2 += (long long)v[m].first*(2*m-r-l-1);
    return ossz2 - ossz1 + min(dp[l], dp[l-1]);
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    v.resize(r.size()+b.size()+1);
    int n = 0;
    for(int x : r)
        v[n++] = make_pair(x, 0);
    for(int x : b)
        v[n++] = make_pair(x, 1);
    if(r[0] < b[0])
        v[n++] = make_pair(-1, 0);
    else
        v[n++] = make_pair(-1, 1);
    sort(v.begin(), v.end());

    ossz.resize(n);
    ossz[0] = v[0].first;
    for(int i = 1; i < n; i++)
        ossz[i] = ossz[i-1] + (long long)v[i].first;

    dp.resize(n, INF);
    dp[0] = 0ll;
    for(int i = 1; i < n && v[i].second == v[0].second; i++)
        dp[i] = (long long)i*INF;

    int lastr = -1, lastb = -1, j = -1;
    for(int i = 1; i < n; i++){
        if(v[i].second == 0 && (lastr == -1 || v[i-1].second != 0)){
            lastr = i;
            j = lastr-1;
        }else if(v[i].second == 1 && (lastb == -1 || v[i-1].second != 1)){
            lastb = i;
            j = lastb-1;
        }
        if(lastr == -1 || lastb == -1)
            continue;
        while(j > min(lastb, lastr) && ertek(j, max(lastb, lastr), i) > ertek(j-1, max(lastb, lastr), i))
            j--;

        dp[i] = ertek(j, max(lastb, lastr), i);
    }

	return dp[n-1];
}

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