Submission #335312

#	Time	Username	Problem	Language	Result	Execution time	Memory
335312		doowey	Simfonija (COCI19_simfonija)	C++14	44 / 110	33 ms	2792 KiB

simfonija

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

vector<ll> dif;
vector<ll> pf;

ll calc(int id, ll x){
    return abs(dif[id]+x);
}

int main(){
    fastIO;
    int n, k;
    cin >> n >> k;
    k = n-k;
    if(k == 0){
        cout << 0 << "\n";
        return 0;
    }
    ll a;
    for(int i = 0 ; i < n; i ++ ){
        cin >> a;
        dif.push_back(a);
    }
    for(int i = 0 ; i < n; i ++ ){
        cin >> a;
        dif[i] -= a;
    }
    sort(dif.begin(), dif.end());
    for(int i = 0 ; i < dif.size(); i ++ ){
        pf.push_back(dif[i]);
        if(i){
            pf[i] += pf[i - 1];
        }
    }
    int l = 0, r = k-1;
    ll cur;
    ll s1, s2;
    ll soln = (ll)1e18;
    for(int i = 0 ; i < n; i ++ ){
        cur = -dif[i];
        while(l < i && r + 1 < n){
            if(r < i || calc(l,cur) + calc(r,cur) >= calc(l+1,cur) + calc(r+1,cur)){
                l++;
                r++;
            }
            else{
                break;
            }
        }
        s1 = pf[i];
        if(l > 0) s1 -= pf[l-1];
        s1 += (i-l+1) * 1ll * cur;
        s2 = pf[r]-pf[i];
        s2 += (r-i) * 1ll * cur;
        soln = min(soln,s2-s1);
    }
    cout << soln << "\n";
    return 0;
}

Compilation message (stderr)

simfonija.cpp: In function 'int main()':
simfonija.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0 ; i < dif.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11