Submission #102521

#	Time	Username	Problem	Language	Result	Execution time	Memory
102521		Nnandi	Simfonija (COCI19_simfonija)	C++14	110 / 110	129 ms	4984 KiB

simfonija

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
typedef long long ll;
ll a[maxn], b[maxn], d[maxn], pf[maxn];
int n, k;

ll get_on(int p1, int p2) {
    if(p2 < p1) return 0LL;
    return pf[p2] - (p1 == 0 ? 0LL : pf[p1-1]);
}

int main()
{
    cin>>n>>k;
    ll sol = 0LL;
    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++) {
        d[i] = a[i] - b[i];
        sol += abs(d[i]);
    }
    sort(d,d+n);

    for(int i=0;i<n;i++) {
        pf[i] = (i==0 ? d[i] : pf[i-1] + d[i]);

    }


    for(int i=0;i<=k;i++) {
        ll med = (i + i+n-k-1) / 2;
        //cout<<med<<endl;
        ll elol = (med-i) * d[med] - get_on(i,med-1);
        //cout<<(med-i) * d[med] <<" "<< get_on(i,med-1) <<endl;
        ll utan = get_on(med+1, i+n-k-1)  - (i+n-k-1-med) * d[med];
        //cout<<get_on(med+1, i+n-k-1)  <<" "<< (i+n-k-1-med) * d[med]<<endl;
        //cout<<elol<<" "<<utan<<endl;
        sol = min(sol,elol+utan);
    }
    cout<<sol<<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