#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using lint=long long;
using pii=pair<int,int>;
#define pb push_back
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<vector<lint>>blocks;
int n=r.size()+b.size();
{
int i=0,j=0;
if(b.front()<r.front()){
swap(b,r);
}
blocks.pb({});
while(i<r.size()||j<b.size()){
if(i==r.size()||(j<b.size()&&b[j]<r[i])){
swap(i,j);
swap(b,r);
blocks.pb({});
}else{
blocks.back().pb(r[i++]);
}
}
}
lint dp[n+1];
dp[0]=0;
for(int i=1;i<=blocks[0].size();i++){
dp[i]=-1;
}
int pastbeg=1,beg=blocks[0].size()+1;
for(int bid=1;bid<blocks.size();bid++){
//cerr<<"new block\n";
vector<lint>&past=blocks[bid-1],&cur=blocks[bid];
vector<lint>curpref(cur.size());
multiset<lint>mp;
for(int i=past.size()-2;0<=i;i--){
past[i]+=past[i+1];
}
curpref[0]=cur[0];
for(int i=1;i<cur.size();i++){
curpref[i]=curpref[i-1]+cur[i];
}
lint psz=past.size(),csz=cur.size();
lint curmin=LLONG_MAX;
for(int i=0;i<csz;i++){
if(0<=psz-i-1){
if(-1<=psz-i-2&&dp[pastbeg+psz-i-2]!=-1){
lint nval=-past[psz-i-1]+i*past[psz-1]+dp[pastbeg+psz-i-2];
curmin=min(curmin,nval);
}
if(0<=psz-i-1&&dp[pastbeg+psz-i-1]!=-1){
lint nval=-past[psz-i-1]+i*past[psz-1]+dp[pastbeg+psz-i-1];
curmin=min(curmin,nval);
}
}
//cerr<<curmin<<"\n";
dp[beg+i]=curpref[i]+curmin-i*past[psz-1];
}
/*
for(int i=0;i<beg+csz;i++)cerr<<dp[i]<<" ";
cerr<<"\n";
*/
curmin=LLONG_MAX;
for(int i=0;i<psz;i++){
int j=psz-i-1;
if(dp[pastbeg+i-1]!=-1){
lint nval=-past[i]+j*cur[0]+dp[pastbeg+i-1];
curmin=min(curmin,nval);
}
if(dp[pastbeg+i]!=-1){
lint nval=-past[i]+j*cur[0]+dp[pastbeg+i];
curmin=min(curmin,nval);
}
if(j<csz){
lint toval=curmin+curpref[j]-j*cur[0];
dp[j]=min(dp[j],toval);
}
}
/*
for(int i=0;i<beg+csz;i++)cerr<<dp[i]<<" ";
cerr<<"\n";
*/
pastbeg+=past.size();
beg+=cur.size();
}
return dp[n];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | while(i<r.size()||j<b.size()){
| ~^~~~~~~~~
wiring.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | while(i<r.size()||j<b.size()){
| ~^~~~~~~~~
wiring.cpp:21:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if(i==r.size()||(j<b.size()&&b[j]<r[i])){
| ~^~~~~~~~~~
wiring.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if(i==r.size()||(j<b.size()&&b[j]<r[i])){
| ~^~~~~~~~~
wiring.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i=1;i<=blocks[0].size();i++){
| ~^~~~~~~~~~~~~~~~~~
wiring.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int bid=1;bid<blocks.size();bid++){
| ~~~^~~~~~~~~~~~~~
wiring.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=1;i<cur.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-9223372036854753826' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '904', found: '-9223372036854775430' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '17703', found: '-9223372036854758087' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '27', found: '-9223372036854775785' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-9223372036854753826' |
| 2 |
Halted |
0 ms |
0 KB |
- |
