#include <bits/stdc++.h>
using namespace std;
using str = std::string;
template<typename _t> using vec = std::vector<_t>;
template<typename _t> using dbl = std::pair<_t, _t>;
using ll = long long;
using sz = size_t;
#define _mp make_pair
#define _mt make_tuple
#define _f first
#define _s second
#define _ot cout <<
#define _in cin >>
#define _er cerr <<
#define _p << ' ' <<
#define _nl '\n'
#define _el << _nl
#define _rg(i, s, e) for (auto i = s; i < e; ++i)
#define _up(i, e) _rg(i, 0, e)
#define _dn(i, s, e) for (auto i = s; i > e; --i)
#define _fr(i, s, e, j) for (auto i = s; i < e; i += j)
#define _elif else if
#define _fn auto
#define _var auto
#define _cexpr constexpr
_fn solve(vec<int> &lens) -> int {
sort(lens.begin(), lens.end());
int sum = 0, ix = 0;
vec<int> prefix(lens.size());
vec<int> suffix(lens.size());
for_each(lens.begin(), lens.end(), [&sum, &ix, &prefix](int n) {
prefix[ix++] = (sum += n);
});
sum = 0, ix = 0;
for_each(lens.rbegin(), lens.rend(), [&sum, &ix, &suffix](int n) {
suffix[ix++] = (sum += n);
});
vec<int> done(lens.size()); iota(done.begin(), done.end(), 1);
vec<int> left(lens.size()); iota(left.rbegin(), left.rend(), 1);
int res = INT_MAX;
int i = lens[lens.size()/2];
auto before = lower_bound(lens.begin(), lens.end(), i)-1;
auto after = upper_bound(lens.begin(), lens.end(), i);
auto before_ix = before - lens.begin();
auto after_ix = after - lens.begin();
auto n_before = done[before_ix];
auto n_after = left[after_ix];
auto sum_before = prefix[before_ix];
auto sum_after = suffix[after_ix];
res = min(res, ((i*n_before) - sum_before)
+ (sum_after - (i*n_after)));
return res;
}
int n, m;
_fn main() -> int {
iostream::sync_with_stdio(false);
cin.tie(0);
_in n >> m;
assert(n == 1);
vec<int> lens(m);
_up(i, m) {
int tmp;
_in tmp >> lens[i];
}
_ot solve(lens) _el;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
