Submission #319512

#	Time	Username	Problem	Language	Result	Execution time	Memory
319512		lohacho	Wiring (IOI17_wiring)	C++14	100 / 100	101 ms	18028 KiB

wiring

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

using namespace std;

using LL = long long;
const LL NS = (LL)2e5 + 4;
LL N, M;
map<LL, LL> last;
vector<pair<LL, LL>> tow;
LL near[NS], dp[NS], pref[NS];

long long min_total_length(vector<int> r, vector<int> b) {
    N = (LL)r.size(), M = (LL)b.size();
    LL A = 0, B = 0;
    while(A < (LL)r.size() && B < (LL)b.size()){
        if(r[A] < b[B]){
            tow.push_back({r[A], 0});
            ++A;
        }
        else{
            tow.push_back({b[B], 1});
            ++B;
        }
    }
    while(A < (LL)r.size()){
        tow.push_back({r[A], 0});
        ++A;
    }
    while(B < (LL)b.size()){
        tow.push_back({b[B], 1});
        ++B;
    }
    LL lpos[2] = {-(LL)1e9, -(LL)1e9};
    for(LL i = 0; i < (LL)tow.size(); ++i){
        near[i] = tow[i].first - lpos[1 - tow[i].second];
        lpos[tow[i].second] = tow[i].first;
    }
    lpos[0] = lpos[1] = (LL)2e9;
    for(LL i = (LL)tow.size() - 1; i >= 0; --i){
        near[i] = min(near[i], lpos[1 - tow[i].second] - tow[i].first);
        lpos[tow[i].second] = tow[i].first;
    }
    for(LL i = 0; i < (LL)tow.size(); ++i){
        if(tow[i].second == 0){
            tow[i].second = -1;
        }
        pref[i] = tow[i].first * tow[i].second;
        if(i){
            pref[i] += pref[i - 1];
        }
    }
    dp[0] = near[0];
    last[tow[0].second] = 1;
    LL zero = 0;
    for(LL i = 1; i < (LL)tow.size(); ++i){
        dp[i] = dp[i - 1] + near[i];
        last[zero] = i + 1;
        zero -= tow[i].second;
        LL j = last[zero] - 1;
        if(j >= 0){
            if(j){
                dp[i] = min(dp[i], dp[j - 1] + abs(pref[i] - pref[j - 1]));
            }
            else{
                dp[i] = min(dp[i], abs(pref[i]));
            }
        }
    }
    return dp[(LL)tow.size() - 1];
}

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