题意
题目等价于：现在有一些物品，每个物品有价格和与之对应的价值，以及拥有的钱数 \(M\)。设 \(V\) 是用 \(M\) 元所能获得的最大价值。对于每一个物品求：如果不能选这个物品，对最大价值 \(V\) 的影响。
思路
遇到有一个不选的这类问题，一般都会使用缺一分治。考虑令 solve(l, r) 为 除了 从 \(l\) 到 \(r\) 的贡献之外的贡献，然后可以直接跑背包记录状态，不难发现分治到最底层就是除了这一个数的贡献，复杂度 \(O(NM \log N)\)。
考虑如何统计答案：如果不选这个物品但是最大价值 \(V\) 没有改变，则答案为 \(A\)；如果不选这个物品但是价值 \(V\) 没有改变，并且选了这个物品之后价值 \(V\) 仍没有改变，则答案为 \(B\)，否则为 \(C\)。
记得开long long。
代码
constexpr int N = 6e4 + 20;
int n, m, p[N], v[N], val, dp[N], V, tmp[60][N];
char b[N];
inline void solve(int l, int r, int tt){if(l == r){if(dp[m] < V) b[l] = 'A';else if(dp[m - p[l]] + v[l] == V) b[l] = 'B';else b[l] = 'C';return;}int mid = (l + r) >> 1;for(int i = 0; i <= m; ++i) tmp[tt][i] = dp[i];for(int i = l; i <= mid; ++i) for(int j = m; j >= p[i]; j--) dp[j] = max(dp[j], dp[j - p[i]] + v[i]);solve(mid + 1, r, tt + 1);for(int i = 0; i <= m; ++i) dp[i] = tmp[tt][i];for(int i = mid + 1; i <= r; ++i)for(int j = m; j >= p[i]; j--) dp[j] = max(dp[j], dp[j - p[i]] + v[i]);solve(l, mid, tt + 1);for(int i = 0; i <= m; ++i) dp[i] = tmp[tt][i];
}
signed main(){n = rd(), m = rd();for(int i = 1; i <= n; ++i) p[i] = rd(), v[i] = rd();for(int i = 1; i <= n; ++i)for(int j = m; j >= p[i]; --j) dp[j] = max(dp[j], dp[j - p[i]] + v[i]);V = dp[m];memset(dp, 0, sizeof(dp));solve(1, n, 0);for(int i = 1; i <= n; ++i) cout << b[i];return 0;
}