/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の仕事の依頼を受けています。それぞれの仕事には 1 から N までの番号が付けられており、仕事 i を引き受けると報酬として A_i 円を得ることができます。
高橋君はこれらの仕事の中からいくつかを選んで引き受けようとしています。各仕事は引き受けるか引き受けないかのいずれかであり、少なくとも 1 つは引き受けなければなりません。
ただし、番号が連続する仕事を両方とも引き受けると、スケジュールの調整に手間がかかるため、追加コストが発生します。具体的には、i = 1, 2, \ldots, N-1 のそれぞれについて、仕事 i と仕事 i + 1 の両方を引き受けた場合、K 円の追加コストがかかります。
高橋君の最終的な利益は、次の式で計算されます。
\text{（利益）} = \text{（引き受けた仕事の報酬の合計）} - K \times \text{（引き受けた仕事の中で番号が連続するペアの数）}
ここで「番号が連続するペアの数」とは、1 \leq i \leq N-1 であって仕事 i と仕事 i+1 の両方を引き受けているような i の個数を指します。
高橋君が N 個の仕事から 1 つ以上を選んで引き受けたとき、得られる利益の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、仕事の個数を表す整数 N と、番号が連続するペア 1 組あたりの追加コストを表す整数 K が、空白区切りで与えられる。
- 2 行目には、各仕事の報酬を表す整数 A_1, A_2, \ldots, A_N が、空白区切りで与えられる。
出力
高橋君が得られる利益の最大値を 1 行で出力せよ。
入力例 1
3 5 4 3 2
出力例 1
6
入力例 2
5 10 8 15 7 12 6
出力例 2
27
入力例 3
10 100 50 120 80 200 30 150 90 60 110 70
出力例 3
600
Score : 366 pts
Problem Statement
Takahashi has received requests for N jobs. Each job is numbered from 1 to N, and if he accepts job i, he receives a reward of A_i yen.
Takahashi plans to select and accept some of these jobs. Each job is either accepted or not accepted, and he must accept at least 1 job.
However, if he accepts both of two consecutively numbered jobs, additional costs are incurred due to the effort of adjusting his schedule. Specifically, for each i = 1, 2, \ldots, N-1, if he accepts both job i and job i + 1, an additional cost of K yen is incurred.
Takahashi's final profit is calculated by the following formula:
\text{(Profit)} = \text{(Total reward of accepted jobs)} - K \times \text{(Number of consecutively numbered pairs among accepted jobs)}
Here, "the number of consecutively numbered pairs" refers to the number of i satisfying 1 \leq i \leq N-1 such that both job i and job i+1 are accepted.
Find the maximum profit Takahashi can obtain when he selects and accepts one or more jobs from the N jobs.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of jobs and an integer K representing the additional cost per consecutively numbered pair, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the reward for each job, separated by spaces.
Output
Print the maximum profit Takahashi can obtain in one line.
Sample Input 1
3 5 4 3 2
Sample Output 1
6
Sample Input 2
5 10 8 15 7 12 6
Sample Output 2
27
Sample Input 3
10 100 50 120 80 200 30 150 90 60 110 70
Sample Output 3
600