제출 #1060994

#제출 시각아이디문제언어결과실행 시간메모리
1060994Faisal_Saqib전선 연결 (IOI17_wiring)C++17
0 / 100
0 ms348 KiB
#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];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...