Submission #1009964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009964		IS_Rushdi	Wiring (IOI17_wiring)	C++17	100 / 100	47 ms	12740 KiB

wiring

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

const ll inf = 1e10;
ll min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size();
    int m = b.size();
    ll ans = 0;
    
    vector<pair<ll,int>>pre(1); pre[0] = {0,-1};
    for(int i = 0; i < n; i++) pre.push_back({r[i],0});
    for(int i = 0; i < m; i++) pre.push_back({b[i],1});
    n +=m;
    sort(pre.begin(),pre.end());
    ll q[2] = {-inf,-inf};
    ll d[n+1]; fill(d,d+n+1,inf);
    for(int i = 1; i <= n; i++){
        q[pre[i].second] = pre[i].first;
        d[i] = min(d[i] , pre[i].first - q[pre[i].second^1]);
    }
    q[0] = q[1] = inf;
    for(int i = n; i >= 1; i--){
        q[pre[i].second] = pre[i].first;
        d[i] = min(d[i] , q[pre[i].second^1]-pre[i].first);
    }
    for(int i = 1; i <= n; i++) pre[i].first += pre[i-1].first;
    
    ll dp[n+1]; fill(dp,dp+n+1,1e18); dp[0] = 0;
    ll nums[n+1]; fill(nums,nums+n+1,0);
    function<ll(int l,int r)>get=[&](int l,int r){
        return pre[r].first - pre[l-1].first;
    };
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i-1] + d[i];
        if(pre[i].second == pre[i-1].second) nums[i] = nums[i-1]+1;
        else nums[i] = 1;

        if(nums[i] <= nums[i-nums[i]]){
            dp[i] = min(dp[i],
            get(i-nums[i]+1 , i) - get(i-nums[i]*2+1 , i-nums[i]) + dp[i-nums[i]*2]
            );
        }
    }
	return dp[n];
}

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

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:10:8: warning: unused variable 'ans' [-Wunused-variable]
   10 |     ll ans = 0;
      |        ^~~

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