This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[200001]={0};
ll pref[200001]={0};
ll min_total_length(vector<int> r, vector<int> b) {
int n=r.size(),m=b.size();
vector<pair<int,int>> a;
for(int v : r)a.push_back({v,0});
for(int v : b)a.push_back({v,1});
sort(a.begin(),a.end());
for(int i=0;i<n+m;i++){
pref[i+1]=pref[i]+a[i].first;
}
// for(int i=0;i<n+m;i++)cout << a[i].first << ' ';
// cout << '\n';
// for(int i=0;i<=n+m;i++)cout << pref[i] << ' ';
// cout << '\n';
int prev_begin=-1,prev_end=-1;
for(int i=1;i<n+m;i++){
if(a[i].second!=a[i-1].second){
prev_begin=prev_end+1;
prev_end=i-1;
}
if(prev_begin==-1)continue;
if(prev_begin==0){
dp[i]=LLONG_MAX/4;
int x=(prev_end-prev_begin+1),y=i-prev_end;
if(x<=y){
dp[i]=(a[prev_end].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y);
// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n';
}else{
dp[i]=(a[prev_end+1].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y);
// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n';
}
continue;
}
dp[i]=LLONG_MAX/4;
for(int j=prev_begin;j<=prev_end;j++){
int x=(prev_end-j+1),y=i-prev_end;
if(x<=y){
dp[i]=min(dp[i],(a[prev_end].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y)+dp[j-1]);
// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n';
}else{
dp[i]=min(dp[i],(a[prev_end+1].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y)+dp[j-1]);
// cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n';
}
}
}
// cout << "\n\n";
// for(int i=0;i<n+m;i++)cout << dp[i] << ' ';
// cout << "\n\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |