Submission #418761

#	Time	Username	Problem	Language	Result	Execution time	Memory
418761		2fat2code	Wiring (IOI17_wiring)	C++17	100 / 100	130 ms	19256 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 200005;

long long n, m, dp[nmax], sum[nmax];
set<long long>s[2];
vector<pair<long long,long long>>vecc;

long long min_total_length(vector<int> r, vector<int> b){
    n = (int)r.size();
    m = (int)b.size();
    for(int i=0;i<n;i++){
        s[0].insert(r[i]);
        vecc.push_back({r[i], 0});
    }
    for(int i=0;i<m;i++){
        s[1].insert(b[i]);
        vecc.push_back({b[i], 1});
    }
    sort(all(vecc));
    for(int i=0;i<(int)vecc.size();i++){
        sum[i+1] = sum[i] + vecc[i].fr;
    }
    int sz_last = 0, sz_curr = 0;
    for(int i=0;i<n+m;i++){
        dp[i+1] = 1e18;
        // case 1
        auto it = s[vecc[i].sc ^ 1].lower_bound(vecc[i].fr);
        if(it != s[vecc[i].sc^1].begin()){
            --it;
            if(vecc[i].sc == vecc[i-1].sc) dp[i+1]=min(dp[i+1], dp[i]+vecc[i].fr-(*it));
            else{
                dp[i+1]=min(dp[i+1],dp[i-1]+vecc[i].fr-(*it));
            }
            it++;
        }
        // case 2
        if(i > 0){
            if(vecc[i].sc != vecc[i-1].sc){
                sz_last = sz_curr;
                sz_curr = 0;
            }
        }
        sz_curr++;
        if(sz_curr <= sz_last){
            int indx = i - sz_curr - sz_curr + 1;
            dp[i+1]=min(dp[i+1], dp[indx]+sum[i+1]-sum[i+1-sz_curr]-(sum[i+1-sz_curr]-sum[i+1-sz_curr-sz_curr]));
        }
        // case 3
        if(it != s[vecc[i].sc^1].end()){
            dp[i+1]=min(dp[i+1],dp[i]+(*it)-vecc[i].fr);
        }
    }
    return dp[n+m];
}

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