Submission #100579

#	Time	Username	Problem	Language	Result	Execution time	Memory
100579		fbosnjak	Simfonija (COCI19_simfonija)	C++14	99 / 110	53 ms	4596 KiB

simfonija

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

#define ll long long

ll N, K;
ll a[100100], b[100100];
vector <ll> v;

ll sol = 1e18;
ll low, high, curr, sum, lok, bris_sum;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
    }

    if (K == N) {cout << 0; return 0;}

    for (int i = 0; i < N; i++)
    {
        v.push_back(a[i] - b[i]);
    }

    sort(v.begin(), v.end());

    /*for (int i = 0; i < N; i++)
    {
        cout << v[i] << ' ';
    }
    cout << endl;*/

    low = 0;
    high = N - K;
    curr = v[0];

    for (int i = 0; i < N; i++)
    {
        sum += abs(curr - v[i]);
    }

    int sz = (int)v.size();

    while (lok < sz && v[lok] <= curr) lok++;

    //cout << lok << endl;

    for (int i = N - K; i < N; i++)
    {
        bris_sum += (v[i] - curr);
    }

    //cout << sum << ' ' << bris_sum << endl;

    sol = sum - bris_sum;

    //cout << "high " << high << endl;

    for (int i = curr + 1; i <= v[sz - 1]; i++)
    {
        sum += lok;
        sum -= (N - lok);

        //cout << "sum " << sum << endl;

        while (lok < sz && v[lok] <= i) lok++;

        bris_sum += low;
        bris_sum -= (N - high);

        if (K > 0)
        {
            //cout << "uso sam " << endl;
            //cout << high << ' ' << N << endl;
            //cout << abs(v[low] - i) << ' '  << abs(v[high] - i) << endl;
            while (high < N && abs(v[low] - i) >= abs(v[high] - i))
            {
                bris_sum -= abs(v[high] - i);
                bris_sum += abs(v[low] - i);

                low++;
                high++;
            }
        }

        //cout << "bris_sum " << bris_sum << endl;

        sol = min(sol, sum - bris_sum);
    }

    cout << sol;
}

• 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: 0 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11