#include "wiring.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define S second
#define F first
using namespace std;
typedef long long ll;
deque<pair<ll,ll> >v;
vector<int>a,b;
ll dp[200009],id[200009][2];
ll best(ll d)
{
if(d==v.size())
return 0;
ll &r=dp[d];
if(r!=-1)
return r;
r=1e16;
if(v[d].S==0)
{
ll x=upper_bound(all(b),v[d].F)-b.begin(),sum;
if(x>0)
{
x--;
sum=abs(b[x]-v[d].F);
if(b[x]>=v[d].F)
r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
else
r=min(r,best(d+1)+sum);
x++;
}
if(x<v.size())
{
sum=abs(b[x]-v[d].F);
if(b[x]>=v[d].F)
r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
else
r=min(r,best(d+1)+sum);
}
}
else
{
ll x=upper_bound(all(a),v[d].F)-a.begin(),sum;
if(x>0)
{
x--;
sum=abs(a[x]-v[d].F);
if(a[x]>v[d].F)
r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
else
r=min(r,best(d+1)+sum);
x++;
}
if(x<v.size())
{
sum=abs(a[x]-v[d].F);
if(a[x]>v[d].F)
r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
else
r=min(r,best(d+1)+sum);
}
}
return r;
}
long long min_total_length(vector<int> o1, vector<int>o2 )
{
sort(all(o1));
sort(all(o2));
a=o1,b=o2;
ll i=0,j=0;
while(i<o1.size()&&j<o2.size())
{
if(o1[i]<=o2[j])
{
id[i][0]=v.size();
v.push_back({o1[i++],0});
}
else
{
id[j][1]=v.size();
v.push_back({o2[j++],1});
}
}
while(i<o1.size())
{
id[i][0]=v.size();
v.push_back({o1[i++],0});
}
while(j<o2.size())
{
id[j][1]=v.size();
v.push_back({o2[j++],1});
}
memset(dp,-1,sizeof dp);
return best(0);
}
Compilation message
wiring.cpp: In function 'll best(ll)':
wiring.cpp:13:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | if(d==v.size())
| ~^~~~~~~~~~
wiring.cpp:32:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if(x<v.size())
| ~^~~~~~~~~
wiring.cpp:54:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if(x<v.size())
| ~^~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:71:12: 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]
71 | while(i<o1.size()&&j<o2.size())
| ~^~~~~~~~~~
wiring.cpp:71:25: 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]
71 | while(i<o1.size()&&j<o2.size())
| ~^~~~~~~~~~
wiring.cpp:84:12: 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]
84 | while(i<o1.size())
| ~^~~~~~~~~~
wiring.cpp:89:12: 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]
89 | while(j<o2.size())
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1740 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25597' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1868 KB |
3rd lines differ - on the 1st token, expected: '904', found: '889' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1868 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1740 KB |
3rd lines differ - on the 1st token, expected: '17703', found: '17658' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1868 KB |
3rd lines differ - on the 1st token, expected: '27', found: '22' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1740 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25597' |
2 |
Halted |
0 ms |
0 KB |
- |