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;
const int MX=200'005;
/*
4 5
1 2 3 7
0 4 5 9 10
*/
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n=r.size();
int m=b.size();
vector<pair<ll,bool>> a;
a.push_back({-1,0});
for(int i=0; i<n; i++){
a.push_back({r[i],0});
}
for(int i=0; i<m; i++){
a.push_back({b[i],1});
}
sort(a.begin(),a.end());
ll dp[MX];
dp[0]=0;
ll soma_b[MX], soma_r[MX];
for(int i=1; i<=n+m; i++){
soma_b[i]=soma_b[i-1];
soma_r[i]=soma_r[i-1];
if(a[i].second){
soma_b[i]+=a[i].first;
}else{
soma_r[i]+=a[i].first;
}
}
int temp[2*MX];
int indice_anterior[MX];
memset(temp,-1, sizeof(temp));
memset(indice_anterior,-1,sizeof(indice_anterior));
int j=n+m;
temp[n+m]=0;
for(int i=1; i<=n+m; i++){
if(a[i].second){
j++;
}else{
j--;
}
if(temp[j]!=-1){
indice_anterior[i]=temp[j];
}
temp[j]=i;
}
for(int i=1; i<=n+m; i++){
//cout<<"->"<<i<<' '<<dp[i-1]<<'\n';
ll ans=MX;
if(a[i].second){
auto u=lower_bound(r.begin(),r.end(),a[i].first);
if(u!=r.end()) ans=min(ans,*u-a[i].first);
if(u!=r.begin()){
u--;
ans=min(ans,a[i].first-*u);
}
}else{
auto u=lower_bound(b.begin(),b.end(),a[i].first);
if(u!=b.end()) ans=min(ans,*u-a[i].first);
if(u!=b.begin()){
u--;
ans=min(ans,a[i].first-*u);
}
}
dp[i]=dp[i-1]+ans;
if(indice_anterior[i]!=-1){
dp[i]=min(dp[i],dp[indice_anterior[i]]+abs((soma_r[i]-soma_r[indice_anterior[i]])-(soma_b[i]-soma_b[indice_anterior[i]])));
}
}
return dp[n+m];
}
# | 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... |