Submission #1060994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060994		Faisal_Saqib	Wiring (IOI17_wiring)	C++17	0 / 100	0 ms	348 KiB

wiring

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long min_total_length(std::vector<int> RR, std::vector<int> BB)
{
    vector<pair<ll,ll>> tp;
	for(auto i:RR)tp.push_back({i,0});
	for(auto i:BB)tp.push_back({i,1});
    sort(begin(tp),end(tp));
    ll n=tp.size();
    ll dp[n+1]={0};
    dp[0]=0;
    for(int i=1;i<=n;i++)
        dp[i]=1e15;
    for(int i=1;i<=n;i++)
    {
        // cout<<"Computing dp for "<<i<<endl;
        int j=i-1;
        ll sm=0;
        ll len=0;
        ll last=0;
        while(j>=0 and tp[j].second==tp[i-1].second)
        {
            len++;
            sm+=tp[j].first;
            last=tp[j].first;
            j--;
        }
        // cout<<"Reach "<<j<<' '<<sm<<' '<<last<<endl;
        int l=j;
        ll sm1=0,len1=0;
        while(j>=0 and tp[j].second==tp[l].second)
        {
            sm1+=tp[j].first;
            len1++;
            ll cur=dp[j] + (sm-(len*tp[l].first)) + ((len1*last)-sm1) - last + tp[l].first;
            // cout<<"Hola dp updating using "<<j<<' '<<sm<<' '<<len<<' '<<sm1<<' '<<len1<<endl;
            // cout<<"Value "<<last<<' '<<cur<<endl;
            dp[i]=min(dp[i],cur);
            j--;
        }
    }
    return dp[n];
}

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