True or False Test

题目描述

注意：本题时间限制为 3s，为默认值的 1.5 倍。内存限制为 512MB，为默认值的 2 倍。 Bessie 正在参加一场包含 $N$ 道判断题（True/False）的考试（$1\le N\le 2\cdot 10^5$）。对于第 $i$ 道题，如果答对她将获得 $a_i$ 分；如果答错她将失去 $b_i$ 分；如果不作答则得分不变（$0<a_i,b_i\le 10^9$）。 Bessie 因为很聪明所以知道所有答案，但她担心负责监考的 Elsie 会在考试结束后追溯性地更改最多 $k$ 道题，使得 Bessie 在这些题上不再答对。 给定 $Q$（$1\le Q\le N+1$）个候选的 $k$ 值（$0\le k\le N$），对于每个 $k$，在要求 Bessie 必须至少作答 $k$ 道题的前提下，求 Bessie 能保证获得的分数。

输入格式

第一行包含 $N$ 和 $Q$。 接下来 $N$ 行，每行包含 $a_i$ 和 $b_i$。 接下来 $Q$ 行，每行包含一个 $k$ 的值。所有 $k$ 的值互不相同。

输出格式

对每个 $k$ 输出一行答案。

2 3
3 1
4 2
2
1
0

-3
1
7

提示

对于每个 $k$ 值，Bessie 的最优策略都是作答所有题目。 SCORING: Inputs 2-4: $N\le 100$ Inputs 5-7: $Q\le 10$, $N\le 2\cdot 10^5$ Inputs 7-20: 无额外限制。 题目来源：Benjamin Qi

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum