题目翻译
有 $n$ 个节点，每个节点有 $2$ 个参数 $a_i,b_i$。
你时刻 $0$ 在节点 $0$，在节点间往返需要消耗 $1$ 的单位时间。
你在时刻 $t$ 到达第 $i$ 个节点时可以等待 $a_i\times t+b_i$ 后获得 $1$ 的收益。
$T+0.5$ 时刻所有节点都会失效，包括你所在的节点。
求你能得到的最大收益，每个节点不能多次等待，不要求在 $T+0.5$ 时刻之前返回 $0$ 节点。
$1\leq n\leq 2\times 10^5,0\leq a_i,b_i,T\leq 10^9$。
题目思路
考虑 exchange argument。
设目前拥有的访问顺序是最优的，即全部经过且等待之后总时刻最小。
对于相邻的 $i+1=j$，你是时刻 $t$ 到达的，若先等待 $i$ 优于先等待 $j$，需要满足 $1+a_i(t+1)+b_i+1+a_j(t+1+a_i(t+1)+b_i+1)+b_j\lt 1+a_j(t+1)+b_j+1+a_i(t+1+a_j(t+1)+b_j+1)+b_i$。
化简得 $\frac{a_j}{b_j+1}\lt \frac{a_i}{b_i+1}$。
也就是说我们按 $\frac{a_i}{b_i+1}$ 的降序排序得到的访问顺序一定是最优的。
这里的 $a_i=0$ 有点特殊，我们单独先拆出来。
对于 $a_i=0$ 的，设我们还有 $t$ 时间剩余，也就是找到尽可能多的 $b_1,b_2,\dots b_k$ ，满足 $(\sum\limits_{i=1}^{k}b_i)-k\leq t$。
这个显然我们是可以排序之后前缀和处理的。
那么对于 $a_i\neq 0$，既然我们已经钦定了访问顺序的最优策略，就是决定当前点选或不选。
那么 $f_{i,j}$ 表示前 $i$ 个节点你选择了 $j$ 个并且都等待了的最少时间。
这个直接类似背包转移即可。第一维可以压掉。
但是这样的转移有个问题，这是 $\mathcal O(n^2)$ 的无法接受。
发现 $a_i\neq 0$ 的情况，你用的时间是指数级增长的，也就是你最多选择的节点数不超过 $\log_2 T$ 个。
那么第二维大小就是 $\mathcal O(\log_2 T)$ 的了，转移复杂度 $\mathcal O(n\log_2 T)$ 可以接受。
然后直接枚举最后选择多少 $a_i\neq 0$ 的，双指针或二分出你能选多少 $a_i=0$ 的即可。
实现中，如果你需要 dp 数组进行初始化，尽量不要 memset，参数不好会炸 long long。
丑陋代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
const int inf = 2e9;
int n, m;
ll T;
vector<int> cst;
struct store
{
ll a, b;
};
vector<store> v;
ll f[200020][35];
ll pre[200020];
int ans;
int main()
{
cin >> n >> T;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if (!a)
cst.push_back(b);
else
v.push_back({a, b});
}
sort(v.begin(), v.end(), [&](store x, store y)
{ return 1.0 * x.a / (x.b + 1) > 1.0 * y.a / (y.b + 1); });
sort(cst.begin(), cst.end());
for (int i = 1; i <= int(cst.size()); i++)
pre[i] = pre[i - 1] + cst[i - 1];
// for (store i : v)
// cout << i.a << " " << i.b << endl;
m = v.size();
for (int i = 0; i <= m; i++)
for (int j = 0; j <= 30; j++)
f[i][j] = inf;
f[0][0] = 0;
for (int i = 1; i <= m; i++)
{
f[i][0] = 0;
for (int j = 1; j <= min(30, i); j++)
{
f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + 1 + v[i - 1].a * (f[i - 1][j - 1] + 1) + v[i - 1].b);
// cout << f[i][j] << " ";
}
// cout << endl;
}
int pos = cst.size();
for (int i = 0; i <= min(30, m); i++)
{
ll t = T - f[m][i];
if (t < 0)
continue;
while (pre[pos] + pos > t)
pos--;
chkmx(ans, pos + i);
// cout << f[m][i] << " " << i << " " << pre[pos] << " " << pos << endl;
}
cout << ans << endl;
return 0;
}