102613: [AtCoder]ABC261 D - Flipping and Bonus
Description
Score : $400$ points
Problem Statement
Takahashi will toss a coin $N$ times. He also has a counter, which initially shows $0$.
Depending on the result of the $i$-th coin toss, the following happens:
- If it heads: Takahashi increases the counter's value by $1$ and receives $X_i$ yen (Japanese currency).
- If it tails: he resets the counter's value to $0$, without receiving money.
Additionally, there are $M$ kinds of streak bonuses. The $i$-th kind of streak bonus awards $Y_i$ yen each time the counter shows $C_i$.
Find the maximum amount of money that Takahashi can receive.
Constraints
- $1\leq M\leq N\leq 5000$
- $1\leq X_i\leq 10^9$
- $1\leq C_i\leq N$
- $1\leq Y_i\leq 10^9$
- $C_1,C_2,\ldots,C_M$ are all different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $C_1$ $Y_1$ $C_2$ $Y_2$ $\vdots$ $C_M$ $Y_M$
Output
Print the maximum amount of money that Takahashi can receive, as an integer.
Sample Input 1
6 3 2 7 1 8 2 8 2 10 3 1 5 5
Sample Output 1
48
If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.
- In the $1$-st coin toss, the coin heads. Change the counter's value from $0$ to $1$ and receive $2$ yen.
- In the $2$-nd coin toss, the coin heads. Change the counter's value from $1$ to $2$ and receive $7$ yen. Additionally, get $10$ yen as a streak bonus.
- In the $3$-rd coin toss, the coin tails. Change the counter's value from $2$ to $0$.
- In the $4$-th coin toss, the coin heads. Change the counter's value from $0$ to $1$ and receive $8$ yen.
- In the $5$-th coin toss, the coin heads. Change the counter's value from $1$ to $2$ and receive $2$ yen. Additionally, get $10$ yen as a streak bonus.
- In the $6$-th coin toss, the coin heads. Change the counter's value from $2$ to $3$ and receive $8$ yen. Additionally, get $1$ yen as a streak bonus.
In this case, Takahashi receives $2+(7+10)+0+8+(2+10)+(8+1)=48$ yen in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows $C_i$.
As a side note, if he gets head in all $6$ coin tosses, he only receives $2+(7+10)+(1+1)+8+(2+5)+8=44$ yen, which is not the maximum.
Sample Input 2
3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000
Sample Output 2
5000000000
Note that the answer may not fit into a $32$-bit integer type.
Input
题意翻译
高桥会掷 $N$ 次硬币,他还有一个计数器,初始示数为0。 对于第 $i$ 次掷硬币的结果,高桥会做出如下行为: - 如果此次硬币为正面,高桥会将计数器 +1,并且获取 $X_{i}$ 元。 - 如果此次硬币为反面,他会将计数器清零,不收到钱。 另外,有 $M $ 种额外连胜奖励。对于第 $i$ 种连胜奖励,每当计数器示数为 $C_{i}$ 时,奖励 $Y_{i}$ 元。 输出高桥的最大收益。Output
问题描述
高桥将抛一枚硬币$N$次。 他还有一个计数器,初始值为$0$。
根据第$i$次抛硬币的结果,会发生以下情况:
- 如果是正面:高桥将计数器的值增加$1$,并获得$X_i$日元(日本货币)。
- 如果是反面:他将计数器的值重置为$0$,没有获得金钱。
此外,还有$M$种连胜奖励。第$i$种连胜奖励会在计数器显示$C_i$时,每次奖励$Y_i$日元。
找出高桥可以获得的最大金钱数。
约束条件
- $1\leq M\leq N\leq 5000$
- $1\leq X_i\leq 10^9$
- $1\leq C_i\leq N$
- $1\leq Y_i\leq 10^9$
- $C_1,C_2,\ldots,C_M$都是不同的。
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出:
$N$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $C_1$ $Y_1$ $C_2$ $Y_2$ $\vdots$ $C_M$ $Y_M$
输出
打印高桥可以获得的最大金钱数,作为整数。
样例输入1
6 3 2 7 1 8 2 8 2 10 3 1 5 5
样例输出1
48
如果他按照正面,正面,反面,正面,正面,正面的顺序获得硬币,将获得以下金钱数额。
- 在第$1$次抛硬币时,硬币正面朝上。将计数器的值从$0$更改为$1$,并获得$2$日元。
- 在第$2$次抛硬币时,硬币正面朝上。将计数器的值从$1$更改为$2$,并获得$7$日元。此外,获得$10$日元的连胜奖励。
- 在第$3$次抛硬币时,硬币反面朝上。将计数器的值从$2$更改为$0$。
- 在第$4$次抛硬币时,硬币正面朝上。将计数器的值从$0$更改为$1$,并获得$8$日元。
- 在第$5$次抛硬币时,硬币正面朝上。将计数器的值从$1$更改为$2$,并获得$2$日元。此外,获得$10$日元的连胜奖励。
- 在第$6$次抛硬币时,硬币正面朝上。将计数器的值从$2$更改为$3$,并获得$8$日元。此外,获得$1$日元的连胜奖励。
在这种情况下,高桥总共获得了$2+(7+10)+0+8+(2+10)+(8+1)=48$日元,这是可能的最大值。
请注意,每次计数器显示$C_i$时,都可以多次获得连胜奖励。
作为旁注,如果他在所有$6$次抛硬币中都获得正面,则他只获得$2+(7+10)+(1+1)+8+(2+5)+8=44$日元,这不是最大值。
样例输入2
3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000
样例输出2
5000000000
请注意,答案可能不适合$32$位整数类型。