oj.uz

Submission #100294

# Submission time Handle Problem Language Result Execution time Memory
100294 2019-03-10T09:42:07 Z Shtef Simfonija (COCI19_simfonija) C++14
110 / 110
 46 ms 3184 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
int n, k;
ll a[100005], b[100005], sol, sad, lf, rt, sum;
vector <ll> d;
const ll inf = (ll)1e15;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.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 << endl;
    return 0;
}
for(int i = 0 ; i < n ; ++i){
    d.push_back(a[i] - b[i]);
    sum += abs(d[i]);
}
sort(d.begin(), d.end());
ll c = n - k, brl = 0, brr = 0;
for(int i = 0 ; i < c / 2 ; ++i){
    lf += d[i];
    brl++;
    sad += abs(d[i]);
}
for(int i = c / 2 ; i < c ; ++i){
    rt += d[i];
    brr++;
    sad += abs(d[i]);
}
sol = sum;
for(int i = 0 ; i <= k ; ++i){
    ll med = d[i + c / 2];
    ll ovo = brl * med - lf + rt - brr * med;
    sol = min(sol, ovo);
    lf -= d[i];
    lf += med;
    rt -= med;
    rt += d[i + c];
    sad -= abs(d[i]);
    sad += abs(d[i + c]);
}
cout << sol << endl;
 
return 0;
}

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 31 ms 3068 KB Output is correct
2 Correct 33 ms 3120 KB Output is correct
3 Correct 30 ms 3088 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3048 KB Output is correct
2 Correct 36 ms 3084 KB Output is correct
3 Correct 46 ms 3032 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3064 KB Output is correct
2 Correct 35 ms 3184 KB Output is correct
3 Correct 26 ms 3060 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3008 KB Output is correct
2 Correct 32 ms 3068 KB Output is correct
3 Correct 31 ms 3060 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3064 KB Output is correct
2 Correct 33 ms 3060 KB Output is correct
3 Correct 32 ms 3036 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3060 KB Output is correct
2 Correct 33 ms 3112 KB Output is correct
3 Correct 35 ms 3076 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3060 KB Output is correct
2 Correct 29 ms 3068 KB Output is correct
3 Correct 38 ms 3060 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3032 KB Output is correct
2 Correct 44 ms 3000 KB Output is correct
3 Correct 35 ms 3060 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3068 KB Output is correct
2 Correct 28 ms 3060 KB Output is correct
3 Correct 30 ms 3068 KB Output is correct