/* 26.08.25 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) (int)x.size()
const ll INF=1e18;
#include "wiring.h"
ll calculate_score(ll num_back,ll num_front,ll sum_back,ll sum_front,ll mx_back,ll mn_front){
return sum_front-sum_back-max(0LL,num_front-num_back)*mx_back+max(0LL,num_back-num_front)*mn_front;
}
ll min_total_length(vector<signed> r,vector<signed> b){
vector<vector<int>> blocks;
vector<int> nums;
int rptr=0,bptr=0;
vector<int> currblock;
while(rptr<sz(r) || bptr<sz(b)){
currblock.clear();
while(bptr==sz(b) || r[rptr]<b[bptr]){
currblock.push_back(r[rptr++]);
if(rptr==sz(r))break;
}
if(!currblock.empty())blocks.push_back(currblock);
if(bptr==sz(b) && rptr==sz(r))break;
currblock.clear();
while(rptr==sz(r) || b[bptr]<r[rptr]){
currblock.push_back(b[bptr++]);
if(bptr==sz(b))break;
}
if(!currblock.empty())blocks.push_back(currblock);
}
for(auto block:blocks) for(auto x:block) nums.push_back(x);
vector<ll> dp={0};//dp[i] = primeros 'i' contadores que se colocaron
int i=0;
for(int j=0;j<sz(blocks);j++){
if(j==0){
for(int k=0;k<sz(blocks[j]);k++,i++) dp.push_back(INF);
continue;
}
int curr_back=i-1,sum_back=nums[curr_back],far_back=i-sz(blocks[j-1]),num_back=1;
int num_front,sum_front=0,mx_back=nums[i-1],mn_front=nums[i];
//no se puede ir más atrás que far_back
for(int k=0;k<sz(blocks[j]);k++,i++){
num_front=k+1;sum_front+=nums[i];
ll best_score=dp[curr_back]+calculate_score(num_back,num_front,sum_back,sum_front,mx_back,mn_front);
//actualizar back
while(curr_back>far_back){
ll new_score=dp[curr_back-1]+calculate_score(num_back+1,num_front,sum_back+nums[curr_back-1],sum_front,mx_back,mn_front);
if(new_score<best_score || j==1){
best_score=new_score;
sum_back+=nums[curr_back-1];
curr_back--;num_back--;
}else break;
}
dp.push_back(best_score);
}
}
return dp.back();
}
# | 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... |