#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=1e6,M=2e3;
int a[100005],b[100005];
main()
{
int n,m;
cin>>n>>m;
map<int,int>mp;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
for(int i=0;i<n;i++)
mp[a[i]-b[i]]++;
int neg=0,pos=0;
for(auto x:mp){
if(x.F<=0)
neg+=x.S;
else pos+=x.S;
}
int ans=0,anss=1e18;
for(int i=0;i<n;i++)
ans+=abs(a[i]-b[i]);
anss=min(abs(ans),anss);
for(int j=-1;j>=-3e6;j--){
ans-=pos;
ans+=neg;
anss=min(anss,abs(ans));
neg+=mp[-j];
pos-=mp[-j];
if(mp[-j]==0)
mp.erase(-j);
}
ans=0,pos=0,neg=0;
for(int i=0;i<n;i++)
ans+=abs(a[i]-b[i]);
for(auto x:mp)
if(x.F<0)
neg+=x.S;
else pos+=x.S;
for(int j=1;j<=3e6;j++){
ans-=neg;
ans+=pos;
anss=min(anss,abs(ans));
neg-=mp[-j];
pos+=mp[-j];
if(mp[-j]==0)
mp.erase(-j);
}
cout<<anss<<endl;
return 0;
}
Compilation message
simfonija.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
10 | main()
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
391 ms |
292 KB |
Output is correct |
2 |
Correct |
338 ms |
288 KB |
Output is correct |
3 |
Correct |
328 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
664 ms |
2468 KB |
Output is correct |
2 |
Correct |
632 ms |
3300 KB |
Output is correct |
3 |
Correct |
419 ms |
3276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
774 ms |
2468 KB |
Output is correct |
2 |
Correct |
550 ms |
3304 KB |
Output is correct |
3 |
Correct |
479 ms |
3268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
691 ms |
2472 KB |
Output is correct |
2 |
Correct |
510 ms |
1872 KB |
Output is correct |
3 |
Correct |
461 ms |
1840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
375 ms |
1940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
859 ms |
4492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
400 ms |
1848 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
814 ms |
4492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
701 ms |
2156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
488 ms |
1844 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |