AT_abc485_f.Big Bridge
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N items 1,2,…,N, one of each. Item i has a price of ci and a value of vi.
Each time Takahashi crosses a bridge, the price of every item whose price is at least 1 decreases by 1.
For each j=0,1,…,M, find the following value.
- The maximum possible total value of the chosen items when, after Takahashi has crossed the bridge j times, zero or more items are chosen so that their total price is at most M.
有 N 个物品,编号为 1,2,…,N,每个物品各一个。物品 i 的价格为 ci,价值为 vi。
每次高桥君穿过一座桥时,所有当前价格至少为 1 的物品的价格都会减少 1。
对每个 j=0,1,…,M,求以下值:
- 在高桥君穿过桥 j 次之后,从物品中选择零个或多个物品(允许不选),使得所选物品的总价格不超过 M,此时所能获得的最大总价值。
输入格式
The input is given from Standard Input in the following format:
N M
c1 v1
c2 v2
⋮
cN vN
输入从标准输入中按以下格式给出:
N M
c1 v1
c2 v2
⋮
cN vN
输出格式
Print the answers in M+1 lines in total. The k-th line should contain the answer for j=k−1.
总共输出 M+1 行答案。第 k 行应包含 j=k−1 对应的答案。
输入输出样例
输入#1
3 4 1 3 2 5 4 8
输出#1
8 16 16 16 16
输入#2
5 6 4 6 4 7 6 11 2 4 1 2
输出#2
11 17 24 30 30 30 30
输入#3
2 1 1 4 1 7
输出#3
7 11
说明/提示
Sample 1 Explanation:
For j=0, the prices of all items remain as they were initially. Choosing items 1 and 2 makes the total value 8, which is the maximum possible.
For j=1, the prices of all items decrease by 1. Choosing items 1, 2, and 3 makes the total value 16, which is the maximum possible.
Constraints
- 1≤N≤102
- 1≤ci≤M≤104
- 1≤vi≤109
- All input values are integers.
样例 1 解释:
当 j=0 时,所有物品的价格保持初始值不变。选择物品 1 和 2,总价值为 8,这是可能的最大值。
当 j=1 时,所有物品的价格均减少 1。选择物品 1、2 和 3,总价值为 16,这是可能的最大值。
约束条件
- 1≤N≤102
- 1≤ci≤M≤104
- 1≤vi≤109
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?