Submission #100294

#	Time	Username	Problem	Language	Result	Execution time	Memory
100294		Shtef	Simfonija (COCI19_simfonija)	C++14	110 / 110	46 ms	3184 KiB

simfonija

#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 / 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