Submission #1203232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203232		LolkasMeep	Wiring (IOI17_wiring)	C++20	100 / 100	49 ms	6576 KiB

wiring

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;

ll min_total_length(vector<int> r, vector<int> b){
    int n = r.size();
    int m = b.size();

    pair<ll, bool> big[n+m];
    auto comp = [](pair<ll, bool> a, pair<ll, bool> b) {
      	if(a.first < b.first) return true;
        if(a.first > b.first) return false;
        return false;
    };

    for(int i = 0; i < n; i++){
        big[i] = {r[i], true};
    }

    for(int i = 0; i < m; i++){
        big[i+n] = {b[i], false};
    }

    sort(big, big+n+m, comp);

    // for(int i = 0; i < n+m; i++){
    //     cout << big[i].first << " " << big[i].second << '\n';
    // }


    ll dp[n+m+5];
    fill(dp, dp+n+m+5, LLONG_MAX);
    dp[0] = 0;
    ll back = 0;
    for(int i = 0; i < n+m; i+=0){
        int j = i + 1;
        while(j < n+m && big[i].second == big[j].second) j++;
        //j is xclusive
        // cout << "block: " << i << ' ' << j << ' ' << back << '\n';
        
        if(i > 0){
            //connect previous
            for(int k = back; k < i; k++){
                // cout << "set " << dp[k+1] << ' ' << dp[k] + (big[i].first - big[k].first) << '\n';
                dp[k+1] = min(dp[k+1], dp[k] + (big[i].first - big[k].first));
            }
            
            //funny case in edtioral
            ll sm = 0;
            for (int k = i; k < j && 2*i-k-1 >= back; k++){
                sm += big[k].first-big[2*i-k-1].first;
                dp[k+1] = min(dp[k+1], dp[2*i-k-1] + sm);
            }
            
            //connect current
            for(int k = i; k < j; k++){
                dp[k+1] = min(dp[k+1], dp[k] + big[k].first - big[i-1].first);
            }
        }

        back = i;
        i = j;
    }

    // for(int i = 0; i < n+m; i++){
    //     cout << dp[i] << ' ';
    // }
    // cout << '\n';

    return dp[n+m];
}


// int main(){
//     int R[] = {1, 2, 3, 7};
//     int B[] = {0, 4, 5, 9, 10};
//     cout << min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}) << '\n';
//     return 0;
// }

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