oj.uz

Submission #100610

# Submission time Handle Problem Language Result Execution time Memory
100610 2019-03-12T20:22:29 Z dalgerok Simfonija (COCI19_simfonija) C++17
110 / 110
 46 ms 3732 KB 
#include<bits/stdc++.h>
using namespace std;



const int N = 1e5 + 5;




int n, k, a[N], b[N], c[N];
long long pref[N];

inline long long get(int l, int r){
    return pref[r] - pref[l - 1];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        c[i] = b[i] - a[i];
    }
    if(n == k){
        return cout << 0, 0;
    }
    sort(c + 1, c + n + 1);
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + c[i];
    }
    int m = n - k;
    long long ans = 9e18;
    for(int i = m; i <= n; i++){
        int l = i - m + 1, r = i;
        int mid = (r + l) / 2;
        ans = min(ans, (1LL * c[mid] * (mid - l + 1) - get(l, mid)) + (get(mid, r) - 1LL * c[mid] * (r - mid + 1)));
    }
    cout << ans;
}

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 29 ms 2304 KB Output is correct
2 Correct 27 ms 2296 KB Output is correct
3 Correct 25 ms 2296 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2216 KB Output is correct
2 Correct 28 ms 2276 KB Output is correct
3 Correct 31 ms 2296 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2432 KB Output is correct
2 Correct 28 ms 2304 KB Output is correct
3 Correct 26 ms 2312 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2268 KB Output is correct
2 Correct 31 ms 2276 KB Output is correct
3 Correct 36 ms 2296 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2272 KB Output is correct
2 Correct 31 ms 3704 KB Output is correct
3 Correct 33 ms 3704 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2268 KB Output is correct
2 Correct 33 ms 2284 KB Output is correct
3 Correct 30 ms 3704 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2268 KB Output is correct
2 Correct 29 ms 3680 KB Output is correct
3 Correct 33 ms 3732 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2424 KB Output is correct
2 Correct 40 ms 3668 KB Output is correct
3 Correct 32 ms 3704 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2304 KB Output is correct
2 Correct 27 ms 3648 KB Output is correct
3 Correct 33 ms 3696 KB Output is correct