Submission #638504

#	Time	Username	Problem	Language	Result	Execution time	Memory
638504		qwerasdfzxcl	Wiring (IOI17_wiring)	C++17	100 / 100	39 ms	11196 KiB

wiring

///https://cologne.tistory.com/28
#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 1e18;

long long min_total_length(std::vector<int> R, std::vector<int> B) {
    int n = R.size() + B.size();
	vector<pair<int, int>> a = {{0, -1}};
	vector<ll> S(n+1, 0), dp(n+1, INF), B2, prf(n+2, INF), suf(n+2, INF);
    vector<int> Blen;

    ///merge
    int pt = 0;
    R.push_back(1e9+100);
    for (int i=0;i<(int)R.size();i++){
        while(pt<(int)B.size() && B[pt]<R[i]){
            a.emplace_back(B[pt], 1);
            ++pt;
        }

        a.emplace_back(R[i], 0);
    }
    a.pop_back();
    assert((int)a.size()==n+1);

    for (int i=1;i<=n;i++) S[i] = S[i-1] + a[i].first;


    ///dp
    int r;
    dp[0] = 0;
    for (int i=1;i<=n;i=r+1){
        r = i;
        while(r<n && a[r+1].second==a[i].second) ++r;

        ///dp calc
        if (Blen.size() >= 2 && Blen.back()==1) for (int j=i;j<=r;j++) { /// SSS...SS / T / SSS...SS
            dp[j] = min(dp[j], *(++B2.rbegin()) + (S[j] - S[i-1]) - (ll)a[i-1].first * (j-i+1));
        }

        if (Blen.size() >= 1) for (int j=i;j<=r;j++) { /// SSS...SS / TTT...TT
            int cnt = j-i+1;
            dp[j] = min(dp[j], prf[min(cnt, Blen.back())] + (S[j] - S[i-1]) - (ll)a[i-1].first * cnt); /// S count <= T count
            dp[j] = min(dp[j], suf[min(cnt, Blen.back()+1)] + (S[j] - S[i-1]) - (ll)a[i].first * cnt); /// S count >= T count
        }

        if (r==n) break;

        ///Blen, B2, prf, suf calc
        Blen.push_back(r-i+1);
        B2.push_back(INF);
        for (int j=i;j<=r;j++) B2.back() = min(B2.back(), dp[j-1] + (ll)a[r+1].first * (r-j+1) - (S[r] - S[j-1]));

        prf[0] = suf[r-i+2] = INF;
        for (int j=i;j<=r;j++){
            int cnt = r-j+1;
            prf[cnt] = dp[j-1] - (S[r] - S[j-1]) + (ll)a[r].first * cnt;
            suf[cnt] = dp[j-1] - (S[r] - S[j-1]) + (ll)a[r+1].first * cnt;
        }

        for (int j=1;j<=r-i+1;j++) prf[j] = min(prf[j-1], prf[j]);
        for (int j=r-i+1;j;j--) suf[j] = min(suf[j+1], suf[j]);
    }
    return dp[n];
}

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