#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll inf = 2e9;
vector <ll> a;
vector <ll> c;
struct p{
ll nr,tip;
}v[2*N];
ll dp[2*N];
ll ps[2*N + 1];
ll sum(ll l,ll r){
return ps[r + 1] - ps[l];
}
ll min_total_length(vector <int> r,vector <int> b){
ll n = 0;
for(ll i = 0;i < r.size();i++){
v[n++] = {r[i],0};
}
for(ll i = 0;i < b.size();i++){
v[n++] = {b[i],1};
}
sort(v,v + n,[&](p a,p b){
return a.nr < b.nr;
});
for(ll i = 0;i < n;i++){
ps[i + 1] = ps[i] + v[i].nr;
dp[i] = inf;
}
ll i = 0,p = -1;
while(i < n){
ll nxt = i;
while(nxt < n - 1 && v[i].tip == v[nxt + 1].tip)nxt++;
if(p != -1){
///p index of first red
///i index of first blue
///nxt index of last blue
///case 1: right side bigger
ll l = i - 1;
ll r = i;
ll cross = (v[i].nr - v[i - 1].nr);
ll minn = inf;
while(l >= p && r <= nxt){
minn = min(minn,(l == 0?0:dp[l - 1]) + ((i - l)*v[i - 1].nr - sum(l,i - 1)));
//cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
l--;r++;
}
while(r <= nxt){
//cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
r++;
}
///case 2:left side bigger
l = p;
r = nxt;
minn = inf;
while(i - 1 - l > r - i){
minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
l++;
}
while(i - 1 - l < r - i){
r--;
}
while(l < i && r > i - 1){
minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
//cout<<r<<' '<<minn<<' '<<sum(i,r)<<' '<<v[i].nr*(r - i + 1)<<'\n';
dp[r] = min(dp[r],sum(i,r) - v[i].nr*(r - i + 1) + minn);
l++;
r--;
}
/*for(ll j = 0;j < n;j++){
cout<<dp[j]<<' ';
}
cout<<'\n';*/
}
p = i;
i = nxt;
i++;
}
return dp[n - 1];
}
/**
int main(){
ll n,m;
cin>>n>>m;
a.resize(n);
c.resize(m);
for(ll i = 0;i < n;i++){
cin>>a[i];
}
for(ll i = 0;i < m;i++){
cin>>c[i];
}
min_total_length(a,c);
return 0;
}
**/
/**
4 5
1 2 3 7
0 4 5 9 10
**/
Compilation message
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(ll i = 0;i < r.size();i++){
| ~~^~~~~~~~~~
wiring.cpp:22:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(ll i = 0;i < b.size();i++){
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Incorrect |
24 ms |
8452 KB |
3rd lines differ - on the 1st token, expected: '41596985758595', found: '2000000000' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4596 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Incorrect |
33 ms |
10048 KB |
3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
28 ms |
9352 KB |
Output is correct |
3 |
Correct |
31 ms |
9304 KB |
Output is correct |
4 |
Correct |
31 ms |
9296 KB |
Output is correct |
5 |
Correct |
30 ms |
9308 KB |
Output is correct |
6 |
Incorrect |
1 ms |
4440 KB |
3rd lines differ - on the 1st token, expected: '42', found: '43' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 |
Halted |
0 ms |
0 KB |
- |