Submission #752926

#	Time	Username	Problem	Language	Result	Execution time	Memory
752926		the_programmer_of_python	Fireworks (APIO16_fireworks)	C++11	0 / 100	601 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

_cexpr sz _max = 300*1000;
int n, m;
int o[_max], l[_max];

_fn main() -> int {
	iostream::sync_with_stdio(false);
	cin.tie(0);

	static int mi = INT_MAX, ma = 0;

	_in n >> m;
	assert(n == 1);
	o[0] = -1; l[0] = 0;
	_rg(i, 2, n+m+1) {
		_in o[i-1] >> l[i-1];
		o[i-1] -= 1;
		assert(o[i-1] == 0);
		mi = min(mi, l[i-1]);
		ma = max(ma, l[i-1]);
	}
	sort(l, l+n+m);

	int n_below, n_above, cost, target = 0, newcost;
	auto ptr_hi = l+1;
	auto ptr_lo = l+1;
	n_below = 0;
	n_above = m;
	while (!*ptr_hi) { ++ptr_hi; --n_above; }
	cost = 0;
	_rg(p, ptr_hi, ptr_hi+n_above) { cost += (*p) - target; }
	newcost = cost;
	for(;;) {
		++target;
		while ((*ptr_lo) < target) { ++ptr_lo; ++n_below; }
		newcost += n_below;
		newcost -= n_above;
		while (n_above && (*ptr_hi) == target) { ++ptr_hi; --n_above; }
		if (n_above == 0) { cost = newcost; ++newcost; }
		if (newcost > cost) {
			_ot cost _el;
			return 0;
		}
		cost = newcost;
	}
}

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