Submission #1133905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133905		onlk97	Wiring (IOI17_wiring)	C++20	13 / 100	77 ms	16056 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector <int> r,vector <int> b){
    vector <pair <int,int> > vec;
    for (int i=0; i<r.size(); i++) vec.push_back({r[i],0});
    for (int i=0; i<b.size(); i++) vec.push_back({b[i],1});
    sort(vec.begin(),vec.end());
    int n=vec.size();
    vec.insert(vec.begin(),{0,0});
    long long dp[n+1];
    vector <pair <int,int> > rgs;
    for (int i=1; i<=n; i++){
        if (i==1) rgs.push_back({1,1});
        else if (vec[i].second==vec[i-1].second) rgs.back().second++;
        else rgs.push_back({i,i});
    }
    dp[0]=0;
    for (int i=1; i<=rgs[0].second; i++) dp[i]=dp[i-1]+vec[rgs[1].first].first-vec[i].first;
    for (int i=1; i<rgs.size(); i++){
        multiset <long long> ms;
        long long sum=0,cnt=0;
        map <int,long long> mp;
        for (int j=rgs[i-1].second; j>=rgs[i-1].first; j--){
            sum+=vec[rgs[i-1].second].first-vec[j].first;
            cnt++;
            long long val=dp[j-1]+sum+cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
            ms.insert(val);
            mp[cnt]=val;
        }
        sum=0; cnt=0;
        long long rem=1e18;
        for (int j=rgs[i].first; j<=rgs[i].second; j++){
            sum+=vec[j].first-vec[rgs[i].first].first;
            cnt++;
            long long mx=rem+cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
            if (!ms.empty()) mx=min(mx,*ms.begin());
            dp[j]=sum+mx;
            if (mp.find(cnt)!=mp.end()){
                long long val=mp[cnt];
                ms.erase(ms.find(val));
                val-=cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
                rem=min(rem,val);
            }
        }
    }
    return dp[n];
}

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