AT_abc485_f.Big Bridge

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN items 1,2,…,N1,2,\dots,N, one of each. Item ii has a price of cic_i and a value of viv_i.

Each time Takahashi crosses a bridge, the price of every item whose price is at least 11 decreases by 11.

For each j=0,1,…,Mj=0,1,\dots,M, find the following value.

  • The maximum possible total value of the chosen items when, after Takahashi has crossed the bridge jj times, zero or more items are chosen so that their total price is at most MM.

有 NN 个物品,编号为 1,2,…,N1,2,\dots,N,每个物品各一个。物品 ii 的价格为 cic_i,价值为 viv_i。

每次高桥君穿过一座桥时,所有当前价格至少为 11 的物品的价格都会减少 11。

对每个 j=0,1,…,Mj=0,1,\dots,M,求以下值:

  • 在高桥君穿过桥 jj 次之后,从物品中选择零个或多个物品(允许不选),使得所选物品的总价格不超过 MM,此时所能获得的最大总价值。

输入格式

The input is given from Standard Input in the following format:

NN MM
c1c_1 v1v_1
c2c_2 v2v_2
⋮\vdots
cNc_N vNv_N

输入从标准输入中按以下格式给出:

NN MM
c1c_1 v1v_1
c2c_2 v2v_2
⋮\vdots
cNc_N vNv_N

输出格式

Print the answers in M+1M+1 lines in total. The kk-th line should contain the answer for j=k−1j=k-1.

总共输出 M+1M+1 行答案。第 kk 行应包含 j=k−1j=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=0j=0, the prices of all items remain as they were initially. Choosing items 11 and 22 makes the total value 88, which is the maximum possible.
For j=1j=1, the prices of all items decrease by 11. Choosing items 11, 22, and 33 makes the total value 1616, which is the maximum possible.

Constraints

  • 1≤N≤1021 \leq N \leq 10^2
  • 1≤ci≤M≤1041 \leq c_i \leq M \leq 10^4
  • 1≤vi≤1091 \leq v_i \leq 10^9
  • All input values are integers.

样例 1 解释:
当 j=0j=0 时,所有物品的价格保持初始值不变。选择物品 11 和 22,总价值为 88,这是可能的最大值。
当 j=1j=1 时,所有物品的价格均减少 11。选择物品 11、22 和 33,总价值为 1616,这是可能的最大值。

约束条件

  • 1≤N≤1021 \leq N \leq 10^2
  • 1≤ci≤M≤1041 \leq c_i \leq M \leq 10^4
  • 1≤vi≤1091 \leq v_i \leq 10^9
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页