oj.uz

Submission #772220

# Submission time Handle Problem Language Result Execution time Memory
772220 2023-07-03T18:20:12 Z Olympia Simfonija (COCI19_simfonija) C++17
110 / 110
 136 ms 6348 KB 
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <climits>
#include <map>
typedef long long ll;
using namespace std;
const int MIN = - (ll)2e6 - 10;
const int MAX = (ll)2e6 + 10;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<ll,int> oc;
    ll neg_sum = 0, neg_num = n, pos_num = 0, pos_sum = 0;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        a[i] -= x;
        oc[a[i]]++;
        neg_sum += abs(a[i] + MIN);
    }
    sort(a.begin(), a.end());
    ll res = LLONG_MAX;
    int l = k - 1; //0 to l
    int r = n; //r to n - 1
    ll sum_left = 0, sum_right = 0;
    for (int i = 0; i <= l; i++) {
        sum_left += -a[i] - MIN;
    }
    //cout << a[k] << " " << a.back()
    for (ll x = MIN + 1; x <= MAX; x++) { //go from neg to pos
        while (l != -1 and r - 1 < a.size() and -a[l] - x < abs(a[r - 1] + x)) {
            sum_left += x - 1 + a[l];
            sum_right += abs(x - 1 + a[r - 1]);
            l--, r--;
        }
        sum_left -= l + 1;
        sum_right += n - r;
        if (oc.count(- x + 1)) { //this will go from 0 to 1
            pos_num += oc[-x + 1];
            neg_num -= oc[-x + 1];
        }
        assert(sum_left >= 0 and sum_right >= 0 and pos_sum >= 0 and neg_sum >= 0);
        pos_sum += pos_num;
        neg_sum -= neg_num;
        res = min(res, pos_sum + neg_sum - sum_left - sum_right);
    }
    cout << res << '\n';
}

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:44:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (l != -1 and r - 1 < a.size() and -a[l] - x < abs(a[r - 1] + x)) {
      |                            ~~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 212 KB Output is correct
2 Correct 18 ms 212 KB Output is correct
3 Correct 19 ms 212 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3156 KB Output is correct
2 Correct 59 ms 2508 KB Output is correct
3 Correct 41 ms 2516 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3152 KB Output is correct
2 Correct 59 ms 2500 KB Output is correct
3 Correct 44 ms 2584 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3104 KB Output is correct
2 Correct 58 ms 2544 KB Output is correct
3 Correct 40 ms 2508 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1868 KB Output is correct
2 Correct 40 ms 2512 KB Output is correct
3 Correct 53 ms 2516 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 5060 KB Output is correct
2 Correct 117 ms 5064 KB Output is correct
3 Correct 125 ms 5064 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2516 KB Output is correct
2 Correct 50 ms 2516 KB Output is correct
3 Correct 89 ms 2828 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5068 KB Output is correct
2 Correct 50 ms 2520 KB Output is correct
3 Correct 135 ms 6272 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2772 KB Output is correct
2 Correct 120 ms 5136 KB Output is correct
3 Correct 114 ms 5152 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2516 KB Output is correct
2 Correct 50 ms 2500 KB Output is correct
3 Correct 136 ms 6348 KB Output is correct