oj.uz

Submission #111952

# Submission time Handle Problem Language Result Execution time Memory
111952 2019-05-17T00:01:06 Z fredbr Simfonija (COCI19_simfonija) C++17
110 / 110
 51 ms 4244 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4116 KB Output is correct
2 Correct 32 ms 4244 KB Output is correct
3 Correct 32 ms 4216 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4136 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 30 ms 4088 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4216 KB Output is correct
2 Correct 29 ms 4060 KB Output is correct
3 Correct 44 ms 4216 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3584 KB Output is correct
2 Correct 31 ms 4144 KB Output is correct
3 Correct 30 ms 4188 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4172 KB Output is correct
2 Correct 42 ms 4088 KB Output is correct
3 Correct 38 ms 4088 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4032 KB Output is correct
2 Correct 34 ms 4088 KB Output is correct
3 Correct 35 ms 4088 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4120 KB Output is correct
2 Correct 43 ms 4216 KB Output is correct
3 Correct 41 ms 4088 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4088 KB Output is correct
2 Correct 36 ms 4188 KB Output is correct
3 Correct 30 ms 4088 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4216 KB Output is correct
2 Correct 31 ms 4088 KB Output is correct
3 Correct 30 ms 4232 KB Output is correct