Submission #572238

#TimeUsernameProblemLanguageResultExecution timeMemory
572238AGESimfonija (COCI19_simfonija)C++14
44 / 110
116 ms11208 KiB
#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],xx[N*4+10]; 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++) xx[a[i]-b[i]+(int)2e6]++; int neg=0,pos=0; for(int i=0;i<=2e6;i++) neg+=xx[i]; for(int i=2e6+1;i<=4e6;i++) pos+=xx[i]; 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=2e6-1;j>=0;j--){ ans-=pos; ans+=neg; anss=min(anss,abs(ans)); int neww=(int)2e6-j; neww=(int)2e6+neww; neg+=xx[neww]; pos-=xx[neww]; } ans=0,pos=0,neg=0; for(int i=0;i<n;i++) ans+=abs(a[i]-b[i]); for(int i=0;i<2e6;i++) neg+=xx[i]; for(int i=2e6;i<=4e6;i++) pos+=xx[i]; for(int j=2e6+1;j<=4e6;j++){ ans-=neg; ans+=pos; anss=min(anss,abs(ans)); int neww=j-(int)2e6; neww=(int)2e6-neww; neg-=xx[neww]; pos+=xx[neww]; } cout<<anss<<endl; return 0; }

Compilation message (stderr)

simfonija.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...