Submission #676425

#	Time	Username	Problem	Language	Result	Execution time	Memory
676425		Essa2006	Simfonija (COCI19_simfonija)	C++14	55 / 110	34 ms	3408 KiB

simfonija

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (int)(1000000007)
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, k;
    cin>>n>>k;
    vector<int>A(n);
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0, a;i<n;i++){
        cin>>a;
        A[i]-=a;
    }
    sort(all(A));
    vector<int>Pre(n);
    Pre[0]=A[0];
    int ans=1e18;
    for(int i=1;i<n;i++)
        Pre[i]=Pre[i-1]+A[i];
    int md=(n-k)/2;
    for(int i=0;i<n;i++){
        int sum=0;
        if(i+k-1<n){    
           int ind=(md>=i? k+md:md), val=A[ind];
           if(ind<i){
               sum=(val*(ind+1))-Pre[ind];
               int len=(i-1)-(ind+1)+1+(n-1)-(i+k)+1;
               sum+=Pre[n-1]-(i+k?Pre[i+k-1]:0)+(i?Pre[i-1]:0)-Pre[ind]-val*len;
           }
           else{
               sum=Pre[n-1]-Pre[ind]-val*((n-1)-(ind+1)+1);
               int len=i+(ind)-(i+k)+1;
               sum+=val*len-(Pre[ind]-Pre[i+k-1]+(i?Pre[i-1]:0));
           }
        }
        else{
            int l=k-((n-1)-i+1)-1, ind=md+l, val=A[ind];
            sum=(ind-(l)+1)*val-(Pre[ind]-(l?Pre[l-1]:0))+Pre[i-1]-Pre[ind]-val*(i-ind-1);
        }
        ans=min(ans, sum);
    }
    cout<<ans;
}

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