Submission #753007

#	Time	Username	Problem	Language	Result	Execution time	Memory
753007		the_programmer_of_python	Fireworks (APIO16_fireworks)	C++11	0 / 100	1 ms	468 KiB

fireworks

#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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45