oj.uz

Submission #335313

# Submission time Handle Problem Language Result Execution time Memory
335313 2020-12-11T22:51:11 Z doowey Simfonija (COCI19_simfonija) C++14
44 / 110
 43 ms 2792 KB 
#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

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.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2664 KB Output is correct
2 Correct 31 ms 2792 KB Output is correct
3 Correct 27 ms 2664 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2664 KB Output is correct
2 Correct 29 ms 2792 KB Output is correct
3 Correct 27 ms 2664 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2664 KB Output is correct
2 Correct 38 ms 2664 KB Output is correct
3 Incorrect 28 ms 2664 KB Output isn't correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 2780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2792 KB Output is correct
2 Incorrect 28 ms 2664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -