#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll val;
bool operator<(const node& n)const{
return val>n.val;
}
};
long long min_total_length(vector<int> r, vector<int> b) {
r.insert(r.begin(), -1);
b.insert(b.begin(),-1);
vector<ll>adj[r.size()+5];
ll n=r.size()-1,m=b.size()-1;
set<ll>str,stb;
set<node>sttr,sttb;
map<ll,ll>mp;
for(int i=1;i<=n;i++){
str.insert(r[i]);
sttr.insert({r[i]});
mp[r[i]]=i;
}
for(int i=1;i<=m;i++){
stb.insert(b[i]);
sttb.insert({b[i]});
mp[b[i]]=i;
}
str.insert(1000000000000000000);
sttr.insert({-1000000000000000000});
stb.insert(1000000000000000000);
sttb.insert({-1000000000000000000});
for(int i=1;i<=n;i++){
ll lol=*stb.lower_bound(r[i]);
node lol2=*sttb.lower_bound({r[i]});
ll lol3=lol2.val;
if(lol!=1000000000000000000){
adj[i].push_back(mp[lol]);
}
if(lol3!=-1000000000000000000){
adj[i].push_back(mp[lol3]);
}
}
for(int i=1;i<=m;i++){
ll lol=*str.lower_bound(b[i]);
node lol2=*sttr.lower_bound({b[i]});
ll lol3=lol2.val;
if(lol!=1000000000000000000){
adj[mp[lol]].push_back(i);
}
if(lol3!=-1000000000000000000){
adj[mp[lol3]].push_back(i);
}
}
for(int i=1;i<=n;i++){
sort(adj[i].begin(),adj[i].end());
}
map<ll,ll>dp[n+5];
for(int i=1;i<=n;i++){
for(auto& u: adj[i]){
dp[i][u]=1000000000000000000;
dp[i-1][u]=1000000000000000000;
dp[i][u-1]=1000000000000000000;
dp[i-1][u-1]=1000000000000000000;
}
}
// for(int i=1;i<=n;i++){
// for(auto& u: adj[i]){
// cout<<u<<" ";
// }
// cout<<'\n';
// }
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(auto& u: adj[i]){
// cout<<u<<" ";
dp[i][u]=min({dp[i-1][u],dp[i][u-1],dp[i-1][u-1]})+abs(r[i]-b[u]);
}
// cout<<'\n';
}
return dp[n][m];
// return 1;
}
#ifdef LOCAL
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,m;
cin>>n>>m;
vector<int>v,v2;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
v.push_back(x);
}
for(int i=1;i<=m;i++){
ll x;
cin>>x;
v2.push_back(x);
}
cout<<min_total_length(v,v2)<<'\n';
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37607' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '904', found: '943' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '316', found: '348' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Incorrect |
378 ms |
82020 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '373776928' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37607' |
2 |
Halted |
0 ms |
0 KB |
- |