DP への落とし込み

\(B_i > 0\) に注意すると，\(m\) 人での脱出が可能ならば，その手順をなぞることで \(m'\) 人 (\(m' < m\)) での脱出も可能であることが分かります．よって単調性より，\(m\) 人での脱出が可能かどうかで二分探索をすればよいです．

以下では \(m\) 人での脱出が可能かどうかを判定することを考えます．

特定の \(m\) 人のあいだでのみメダルを分配し，ほかの園児を見捨てるものとしてよいです(そうでない手順について，脱出しない園児に分配するぶんを脱出する園児に振り分け直すことで損なく帰着できる)． このとき，対象の \(m\) 人全員が脱出することが求められます．

DP テーブル \(dp[i][x]\) の値を，「\(i\) 日目終了時点で \(x\) 人が会場に残る場合のメダル総数の最大値 (不可能ならば \(-\infty\))」として定めます．\(0 \leq x \leq m\) の範囲を考えればよく，\(dp[0]\) の値は \(\displaystyle dp[0][x] = \begin{cases} 0 & (x = m) \\ -\infty & (x < m) \end{cases}\) です．

このとき，\(dp[i-1]\) から \(dp[i]\) への遷移は以下のようになります．

1. \(dp[i][x] = dp[i-1][x] + A_i - B_i x\)．この値が負ならば \(-\infty\) で置き換える．
2. \(dp[i][x] = \max(dp[i][x], dp[i][x+1] - C_i)\)．この値が負ならば \(-\infty\) で置き換える．

最終的に \(dp[N][0] \leq 0\) であれば可能，\(dp[N][0] = -\infty\) であれば不可能です．

高速化

任意の \(i\) について，以下が成り立つことが帰納法で示せます．

• \(dp[i][x] \neq -\infty\) を満たす \(x\) の範囲は，空 \(\emptyset\) または区間 \([x_l. x_r]\) をなす．
• \(dp[i][x]\) は \(x\) に対して上に凸．

そこで，\(dp[i]\) を折れ線をつなげたグラフとして管理することにすると，遷移の各処理は以下のように書けます．

1. 全体に一次関数 \(A_i - B_i x\) を加えたあと，区間 \([x_l, x_r]\) の左右から値が負の範囲を削る．
2. 左 (\(x\) の小さいほう) から傾き \(C_i\) 以上の線分を削ったあと，左端から傾き \(C_i\) の線分を非負の範囲で伸ばす．

全体に加えた一次関数をまとめて管理し，傾き変化点の座標・線分の傾きを取得する際に逐一適用することで，全体 \(O(N)\) 時間で処理することができます(各 \(i\) で付け加わる線分は高々 \(1\) 本)．

なお，このような折れ線グラフ型 DP の高速化手法を Slope Trick と呼びます．

実装例 (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;
}