103057: [Atcoder]ABC305 Ex - Shojin
Description
Score : $650$ points
Problem Statement
You have decided to practice. Practice means solving a large number of problems in AtCoder.
Practice takes place over several days. The practice for one day is carried out in the following steps.
- Let $M$ be the number of problems to be solved on that day. Each problem has a value called difficulty, which is a pair of non-negative integers $(A, B)$.
- First, rearrange the $M$ problems in any order. Then, solve the problems one by one in that order.
- You have a value called fatigue. The fatigue at the beginning of the day is $0$, and it changes from $x$ to $Ax + B$ when solving a problem with difficulty $(A, B)$.
- The fatigue at the end of solving all $M$ problems is called the energy consumed for that day.
There is a sequence of $N$ problems in AtCoder, called problem $1$, problem $2$, $\dots$, problem $N$ in order. The difficulty of problem $i$ is $(A_i, B_i)$.
You have decided to solve all $N$ problems through practice.
Practice is carried out in the following steps. Below, let $[L, R]$ denote the following sequence of problems: problem $L$, problem $L+1$, $...$, problem $R$.
- Choose an integer $K$ freely between $1$ and $N$, inclusive. The practice will last $K$ days.
- Divide the sequence of $N$ problems into $K$ non-empty continuous subsequences, and let $S_i$ be the $i$-th sequence.
Formally, choose a strictly increasing non-negative integer sequence $x_0, x_1, \dots, x_K$ such that $1 = x_0$ and $x_K = N + 1$, and let $S_i = [x_{i-1}, x_i - 1]$ for $1 \leq i \leq K$. - Then, for $i=1, 2, \dots, K$, solve all problems in $S_i$ on the $i$-th day of practice.
You have decided to practice so that the total energy consumed throughout the practice is at most $X$.
Let $D$ be the minimum possible value of $K$, the number of days, for such a practice. (Here, it is guaranteed that $\sum_{i = 1}^N B_i \leq X$. Under this constraint, such $D$ always exists.)
Also, let $M$ be the minimum possible total energy consumed throughout a practice such that $K=D$.
Find $D$ and $M$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq X \leq 10^8$
- $1 \leq A_i \leq 10^5$
- $1 \leq B_i$
- $\sum_{i=1}^N B_i \leq X$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $X$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
Output
Print $D$ and $M$ separated by a space.
Sample Input 1
3 100 2 2 3 4 5 7
Sample Output 1
1 52
In this test case, you can solve all problems in one day while satisfying the condition for $X$.
By following the steps below, the total energy consumed during the practice will be $52$, which is the minimum.
- Set $K=1$ and solve $[1, 3]$ on the first day.
- Carry out the practice on the first day in the following steps.
- Arrange the problems in the order (problem $3$, problem $2$, problem $1$).
- Initially, the fatigue is $0$.
- Solve problem $3$. The fatigue changes to $5 \times 0 + 7 = 7$.
- Solve problem $2$. The fatigue changes to $3 \times 7 + 4 = 25$.
- Solve problem $1$. The fatigue changes to $2 \times 25 + 2 = 52$.
- The fatigue at the end of solving all problems is $52$. Therefore, the energy consumed on this day is $52$.
- The total energy consumed throughout the practice is also $52$.
Sample Input 2
3 30 2 2 3 4 5 7
Sample Output 2
2 17
This test case is obtained by changing $X$ from $100$ to $30$ in the first test case. Therefore, it is impossible to solve all problems in one day while satisfying the condition for $X$.
By following the steps below, you can achieve $M=17$ by practicing for two days.
- Set $K = 2$, and solve $[1, 2]$ on the first day and $[3, 3]$ on the second day.
- Carry out the practice on the first day in the following steps.
- Arrange the problems in the order (problem $1$, problem $2$).
- Initially, the fatigue is $0$.
- Solve problem $1$. The fatigue changes to $2 \times 0 + 2 = 2$.
- Solve problem $2$. The fatigue changes to $3 \times 2 + 4 = 10$.
- The fatigue at the end of solving all problems is $10$. Therefore, the energy consumed on the first day is $10$.
- Carry out the practice on the second day in the following steps.
- Arrange the problems in the order (problem $3$).
- Initially, the fatigue is $0$.
- Solve problem $3$. The fatigue changes to $5 \times 0 + 7 = 7$.
- The fatigue at the end of solving all problems is $7$. Therefore, the energy consumed on the second day is $7$.
- The total energy consumed throughout the practice is $10 + 7 = 17$.
Sample Input 3
5 50000000 100000 10000000 100000 10000000 100000 10000000 100000 10000000 100000 10000000
Sample Output 3
5 50000000
The optimal practice is to solve one problem per day.
Sample Input 4
10 100000000 5 88 66 4 52 1 3 1 12 1 53 25 11 12 12 2 1 20 47 10
Sample Output 4
2 73647
Sample Input 5
15 100000000 2387 3178 2369 5772 1 29 36 3 52 2981 196 1 36 704 3 3 1501 5185 23 628 3623 810 80 101 6579 15 681 7 183 125
Sample Output 5
4 54468135
Input
题意翻译
## 题目描述 你决定练习，练习意味着在 AtCoder 中解决大量问题。 练习需要几天时间。每天的练习分为以下步骤。 设 $M$ 是当天要解决的问题数。每个问题都有一个称为难度的值，它是一对非负整数（$A$，$B$）。 首先，以任何顺序重新排列 $M$ 个问题。然后，按该顺序逐个解决问题。 您有一个称为疲劳的值。疲劳在开始一天时为 0，当解决难度为（$A$，$B$）的问题时，它从 $x$ 变为 $Ax + B$。 解决所有 $M$ 个问题的疲劳在解决当天的能量消耗中。 在 AtCoder 中有一个 $N$ 个问题的序列，按顺序称为问题 1、问题 2，…，问题 $N$。问题i的难度为（$A_i$，$B_i$）。 您决定通过练习解决所有 $N$ 个问题。 练习分为以下步骤。下面，让 $[L,R]$ 表示以下问题序列：问题 $L$，问题 $L + 1$，$\cdots$，问题 $R$。 自由选择 1 到 $N$（含）之间的整数 $K$。练习将持续 $K$ 天。 将 $N$ 个问题的顺序连续子序列分成 $K$ 个非空连续子序列，并让 $S_i$ 为第 $i$ 个序列。 形式上，选择一个严格递增的非负整数序列 $x_0,x_1,\cdots,x_K$，使得 $1 = x_0$ 且 $x_K = N + 1$，并让 $S_i = [xi-1，xi-1]$ 对于 $1≤i≤K$ 中的所有问题。 然后，对于 $i = 1,2,\cdots,K$，解决第 $i$ 天练习中的所有问题 $S_i$。 你决定练习，使得整个练习中消耗的总能量最多为 $X$。 让 $D$ 是 $K$ 的最小可能值，即天数，以进行这样的练习。（在此约束下，$D$ 始终存在） 还让 $M$ 是在 $K = D$ 的情况下消耗的最小总能量。 找到 $D$ 和 $M$。 ## 输入 输入格式为： $N X$ $A_1 B_1$ $A_2 B_2$ ⋮ $A_N B_N$ ## 输出 输出 $D$ 和 $M$，用空格分隔。Output
得分：$650$分
问题描述
你决定进行练习。练习意味着在AtCoder上解决大量问题。
- 设$M$为当天要解决的问题数量。每个问题都有一个称为难度的值，表示为非负整数对$(A, B)$。
- 首先，以任意顺序重新排列这$M$个问题。然后，按照该顺序逐一解决这些问题。
- 你有一个称为疲劳的值。在一天开始时的疲劳值为$0$，在解决难度为$(A, B)$的问题时，疲劳值会从$x$变为$Ax + B$。
- 解决完所有$M$个问题后的疲劳值称为当天的能量消耗。
AtCoder中有一个称为问题$1$，问题$2$，$\dots$，问题$N$的连续问题序列。问题$i$的难度为$(A_i, B_i)$。
你决定通过练习解决所有$N$个问题。
- 在$1$到$N$（包括$N$）之间自由选择一个整数$K$。练习将持续$K$天。
- 将$N$个问题的序列划分为$K$个非空连续子序列，并将第$i$个序列记为$S_i$。
正式地说，选择一个严格递增的非负整数序列$x_0, x_1, \dots, x_K$，其中$1 = x_0$且$x_K = N + 1$，并且对于$1 \leq i \leq K$，$S_i = [x_{i-1}, x_i - 1]$。 - 然后，在练习的第$i$天解决$S_i$中的所有问题。
你决定进行练习，以便整个练习过程中的总能量消耗不超过$X$。
- 令$D$为满足上述练习的最小可能的天数$K$。在这里，保证了$\sum_{i = 1}^N B_i \leq X$。在该约束下，这样的$D$总是存在。
- 令$M$为满足$K=D$的练习的最小可能的总能量消耗。
找到$D$和$M$。
限制条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq X \leq 10^8$
- $1 \leq A_i \leq 10^5$
- $1 \leq B_i$
- $\sum_{i=1}^N B_i \leq X$
- 所有输入值均为整数。
输入
输入通过标准输入给出以下格式：
$N$ $X$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
输出
以空格分隔的方式打印$D$和$M$。
样例输入 1
3 100 2 2 3 4 5 7
样例输出 1
1 52
在这个测试用例中，你可以在满足$X$的条件下在一天内解决所有问题。
- 设置$K=1$，并在第一天解决$[1, 3]$。
- 按照以下步骤进行第一天的练习，练习过程中的总能量消耗为$52$，这是最小的。
- 设置$K=1$，并在第一天解决$[1, 3]$。
- 按照以下步骤进行第一天的练习，练习过程中的总能量消耗为$52$，这是最小的。
样例输入 2
3 30 2 2 3 4 5 7
样例输出 2
2 17
这个测试用例是通过将$X$从$100$更改为$30$得到的。因此，在满足$X$的条件下，在一天内解决所有问题是不可能的。
按照以下步骤进行两天的练习，可以实现两天的练习总能量消耗为$17$。
- 设置$K = 2$，并在第一天解决$[1, 2]$，在第二天解决$[3, 3]$。
- 按照以下步骤进行第一天的练习，练习过程中的总能量消耗为$10$。
- 按照以下步骤进行第二天的练习，练习过程中的总能量消耗为$7$。
- 两天的练习总能量消耗为$10 + 7 = 17$。
样例输入 3
5 50000000 100000 10000000 100000 10000000 100000 10000000 100000 10000000 100000 10000000
样例输出 3
5 50000000
最优练习是在每天解决一个问题。
样例输入 4
10 100000000 5 88 66 4 52 1 3 1 12 1 53 25 11 12 12 2 1 20 47 10
样例输出 4
2 73647
样例输入 5
15 100000000 2387 3178 2369 5772 1 29 36 3 52 2981 196 1 36 704 3 3 1501 5185 23 628 3623 810 80 101 6579 15 681 7 183 125
样例输出 5
4 54468135