Submission #407378

#	Time	Username	Problem	Language	Result	Execution time	Memory
407378		Peti	Wiring (IOI17_wiring)	C++14	13 / 100	53 ms	8484 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;

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;
}

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;

    vector<long long> dp(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)+dp[j-1] > ertek(j-1, max(lastb, lastr), i)+dp[j-2])
            j--;
        dp[i] = ertek(j, max(lastb, lastr), i)+dp[j-1];
    }

	return dp[n-1];
}

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