Submission #111952

#	Time	Username	Problem	Language	Result	Execution time	Memory
111952		fredbr	Simfonija (COCI19_simfonija)	C++17	110 / 110	51 ms	4244 KiB

simfonija

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int const maxn = 101010;
int const maxm = 1010101;
ll const inf = 0x3f3f3f3f3f3f3f3f;

ll a[maxn], v[maxn];
ll p[maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        v[i] = a[i]-x;
    }

    sort(v+1, v+n+1);

    for (int i = 1; i <= n; i++)
        p[i] = p[i-1] + v[i];

    ll ans = inf;

    for (int l = 1; l + n - k - 1 <= n; l++) {
        int r = l+n-k-1;

        int idx = (l+r)/2;

        int a = idx-l;
        int b = r-idx+1;
        ll soma_a = p[idx-1] - p[l-1];
        ll soma_b = p[r] - p[idx-1];

        ll sum = - soma_a + a*v[idx] + soma_b - b*v[idx];

        sum = abs(sum);

        ans = min(ans, sum);
    }

    cout << ans << "\n";
}

• 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