Designing DP

Since \(B_i > 0\), if \(m\) kids can escape, then \(m'\) kids (\(m' < m\)) can escape too. Thus, by monotonicity, we may binary search and determine if \(m\) kids can escape.

From now on, we consider how to determine if \(m\) kids can escape.

We can fix \(m\) kids and redistribute coins only among them, giving up the others. (For any procedure against this assumption, one can always redistribute the coins for those not escaping eventually to those escaping eventually instead.) In this case, all \(m\) kids are required to escape.

Define the value \(dp[i][x]\) of the DP (Dynamic Programming) table as the maximum total number of medals when \(x\) kids remain at the end of day \(i\) (or \(-\infty\) if it is impossible). It is sufficient to consider the range \(0 \leq x \leq m\). The values for \(dp[0]\) are \(\displaystyle dp[0][x] = \begin{cases} 0 & (x = m) \\ -\infty & (x < m) \end{cases}\).

Then, the transitions from \(dp[i-1]\) to \(dp[i]\) are as follows:

1. Let \(dp[i][x] = dp[i-1][x] + A_i - B_i x\). If this is negative, replace it with \(-\infty\).
2. Let \(dp[i][x] = \max(dp[i][x], dp[i][x+1] - C_i)\). If this is negative, replace it with \(-\infty\).

Finally, the objective is achievable if \(dp[N][0] \leq 0\), and not achievable if \(dp[N][0] = -\infty\).

Optimization

We can prove by induction for any \(i\) that:

• The range of \(x\) with \(dp[i][x] \neq -\infty\) forms an empty set \(\emptyset\), or a segment \([x_l. x_r]\).
• \(dp[i][x]\) is concave with respect to \(x\).

If we manage \(dp[i]\) as a piecewise linear function, the transitions can be represented by the following steps:

1. Globally add the linear function \(A_i - B_i x\), and then scrape the negative region from the both ends of \([x_l, x_r]\).
2. Scrape all segments of slope \(C_i\) or greater from the left end (with smaller \(x\)), and extend a segment of slope \(C_i\) from the left end up to the non-negative range.

By managing the globally added linear function separately, and applying it every time retrieving the coordinates of breakpoints and slopes, it can be processed in a total of \(O(N)\) time. (Every step adds at most one segment.)

Such a DP optimization trick is called Slope Trick (article is in Japanese; you can find English references in the article).

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
#include <algorithm>
using std::sort;
#include <deque>
using std::deque;
#include <cassert>

#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

typedef long long int ll;
typedef pair<ll, ll> pr;

const ll INF = (1LL << 60);
const ll VERTICAL = 1;

ll n;
vector<ll> a, b, c;

ll& chmin (ll &l, const ll &r) {
	return l = min(l, r);
}
ll& chmax (ll &l, const ll &r) {
	return l = max(l, r);
}
template<class T>
void sortall (vector<T> &a) {
	sort(a.begin(), a.end());
}

template<class T>
T& atback (deque<T> &a, int idx) {
	return a.at((int)a.size() - 1 - idx);
}


bool func (const ll m) {
	if (m <= 0) return true;
	ll sa = 0, sb = 0; // mask, y = sa x + sb
	deque<pr> dots = {(pr){m, 0}}; // (x, y) before adding mask, increasing order

	auto evaldot = [&](const pr &p) -> ll {
		return sa * p.first + sb + p.second;
	};
	auto slope = [&](const pr &l, const pr &r) -> ll {
		ll y = r.second - l.second;
		ll x = r.first  - l.first;
		assert(x > 0 && y % x == 0);
		return y / x;
	};
	auto debugoutput = [&](void) -> void {
		if (debug) {
			for (ll i = 0; i < dots.size(); i++) {
				cerr << dots[i].first << " " << dots[i].second << endl;
			}
			cerr << "sa: " << sa << ", sb: " << sb << endl;
		}
	};

	for (ll di = 0; di < n; di++) {
		sb += a[di];
		sa += (-1) * b[di];

		// erase <0 parts from back
		while (true) {
			if (dots.size() == 0) break;
			pr p1 = dots.back();
			ll y1 = evaldot(p1);
			if (y1 >= 0) break;

			dots.pop_back();

			if (dots.size() == 0) break;
			pr p2 = dots.back();
			ll y2 = evaldot(p2);
			if (y2 < 0) continue;
			ll ta = slope(p2, p1);
			assert(sa + ta != 0);
			ll xadd = y2 / (-(sa + ta));
			
			if (xadd > 0) dots.push_back({p2.first + xadd, p2.second + ta * xadd});
			break;
		}
		// erase <0 parts from front
		while (true) {
			if (dots.size() == 0) break;
			pr p1 = dots.front();
			ll y1 = evaldot(p1);
			if (y1 >= 0) break;

			dots.pop_front();

			if (dots.size() == 0) break;
			pr p2 = dots.front();
			ll y2 = evaldot(p2);
			if (y2 < 0) continue;
			ll ta = slope(p1, p2);
			assert(sa + ta != 0);
			ll xadd = y2 / (+(sa + ta));
			
			if (xadd > 0) dots.push_front({p2.first - xadd, p2.second - ta * xadd});
			break;
		}

		if (dots.size() == 0) return false; // fail

		// erase slope>=C from front
		while (true) {
			if (dots.size() <= 1) break;

			ll s = sa + slope(dots[0], dots[1]);
			if (s >= c[di]) {
				dots.pop_front();
				continue;
			} else {
				break;
			}
		}
		// slope C into front
		ll xcadd = evaldot(dots[0]) / c[di];
		if (xcadd >= dots[0].first) {
			return true; // success
		} else if (xcadd > 0) {
			dots.push_front({dots[0].first - xcadd, dots[0].second - (c[di] - sa) * xcadd});
		}
	}

	return false;
}

void solve () {
	ll ok = 0, ng = max(a[0], 0LL) + 1;
	while (ok + 1 < ng) {
		ll med = (ok + ng) / 2;
		if (func(med)) {
			ok = med;
		} else {
			ng = med;
		}
	}

	ll ans = ok;

	cout << ans << "\n";
	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int ti = 0; ti < T; ti++) {
		cin >> n;

		a.resize(n);
		b.resize(n);
		c.resize(n);
		for (ll i = 0; i < n; i++) {
			cin >> a[i] >> b[i] >> c[i];
		}

		solve();
	}
	

	return 0;
}