Submission #105449

#	Time	Username	Problem	Language	Result	Execution time	Memory
105449		igzi	Simfonija (COCI19_simfonija)	C++17	110 / 110	67 ms	4732 KiB

simfonija

#include <bits/stdc++.h>

using namespace::std;

long long a[100005],b[100005],s[100005],n,k,i,ans=LLONG_MAX;
vector <int> v;

long long resi(int l,int d,int x){
long long p=lower_bound(v.begin(),v.end(),x)-v.begin();
p--;
long long res=0;
if(p>=l){res+=(p-l+1)*x;
res-=s[p+1]-s[l];}
p=upper_bound(v.begin(),v.end(),x)-v.begin();
if(p<=d){res+=s[d+1]-s[p];
res-=x*(d-p+1);
}
return res;
}

int main(){
std::ios_base::sync_with_stdio(0);
cin>>n>>k;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n;i++) {cin>>b[i]; v.push_back(2*(a[i]-b[i]));}
sort(v.begin(),v.end());
s[0]=0;
for(i=1;i<=n;i++) s[i]=s[i-1]+v[i-1];
for(i=0;i<k+1;i++){
    int x,m,d;
    d=n-k+i-1;
    if(i>0){
        x=(v[i-1]+v[d])/2;
        ans=min(ans,resi(i,d,x));
    }
    if(d<n-1){
        x=(v[d+1]+v[i])/2;
        ans=min(ans,resi(i,d,x));
    }
    m=(i+d)/2;
    ans=min(ans,resi(i,d,v[m]));
}
cout<<ans/2<<endl;
return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11