AtCoder Weekday Contest 0065 Beta

A - 長距離ドライブの休憩計画

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は N 区間からなる長距離ドライブの計画を立てています。区間には先頭から順に 1, 2, \ldots, N の番号が付いており、第 i 区間を走行するには A_i 時間かかります。高橋君は第 1 区間、第 2 区間、…、第 N 区間の順に走行します。

高橋君は安全のため、以下のルールに従って休憩を取ります。

第 K 区間、第 2K 区間、第 3K 区間、… のように、番号が K の倍数である区間を走り終えた直後、まだ走行すべき区間が残っている場合に 1 時間の休憩を取る。それ以外のタイミングでは休憩を取らない。

すべての区間を走り終えるまでにかかる合計時間（走行時間と休憩時間の総和）を求めてください。なお、合計時間は必ず整数になります。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq N
1 \leq A_i \leq 10^9
入力はすべて整数
この制約の下で、答えは 64-bit 符号付き整数に収まる

入力

入力は以下の形式で与えられます。

N K
A_1 A_2 \cdots A_N

1 行目には、区間の数 N と休憩を挟む間隔 K がスペース区切りで与えられます。

2 行目には、第 i 区間の走行時間 A_i が空白区切りで与えられます。

出力

すべての区間を走り終えるまでにかかる合計時間を 1 行で出力してください。

入力例 1

5 2
3 1 4 1 5

出力例 1

入力例 2

4 4
7 2 8 3

出力例 2

入力例 3

10 3
5 9 2 6 5 3 5 8 9 7

出力例 3

入力例 4

20 6
12 7 25 4 18 9 3 14 11 6 20 5 8 17 13 2 10 16 19 15

出力例 4

入力例 5

1 1
1000000000

出力例 5

1000000000

Score : 200 pts

Problem Statement

Takahashi is planning a long-distance drive consisting of N segments. The segments are numbered 1, 2, \ldots, N from the beginning, and it takes A_i hours to drive through segment i. Takahashi drives through the segments in order: segment 1, segment 2, …, segment N.

For safety, Takahashi takes breaks according to the following rule:

Immediately after finishing segment K, segment 2K, segment 3K, …, that is, immediately after finishing a segment whose number is a multiple of K, he takes a 1-hour break if there are still remaining segments to drive. He does not take breaks at any other time.

Find the total time (the sum of driving time and break time) it takes to finish driving all segments. Note that the total time is always an integer.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K \leq N
1 \leq A_i \leq 10^9
All inputs are integers
Under these constraints, the answer fits in a 64-bit signed integer

Input

The input is given in the following format:

N K
A_1 A_2 \cdots A_N

The first line contains the number of segments N and the break interval K, separated by a space.

The second line contains the driving time A_i for segment i, separated by spaces.

Output

Print the total time it takes to finish driving all segments in one line.

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

Sample Input 2

4 4
7 2 8 3

Sample Output 2

Sample Input 3

10 3
5 9 2 6 5 3 5 8 9 7

Sample Output 3

Sample Input 4

20 6
12 7 25 4 18 9 3 14 11 6 20 5 8 17 13 2 10 16 19 15

Sample Output 4

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000

B - 買い物リスト

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君はスーパーマーケットで買い物をしています。

店内には一列に並んだ N 個の棚があり、入口に近い方から順に 1 番目、2 番目、…、N 番目と番号が付けられています。i 番目の棚には A_i 個の商品が陳列されています。

高橋君は入口側の 1 番目の棚から順番に棚を見ていき、各棚で買いたい商品の個数を確認していきます。k 番目の棚まで確認し終えた時点で、1 番目から k 番目までの棚の商品数の合計 A_1 + A_2 + \cdots + A_k が初めて X 以上になったとき、手で持ちきれなくなるので買い物かごを取りに入口まで戻ることにします。

高橋君が買い物かごを取りに戻るのは何番目の棚まで確認し終えたときか求めてください。ただし、N 番目の棚まで確認しても合計が X 以上にならない場合は -1 を出力してください。

制約

1 \leq N \leq 5 \times 10^5
1 \leq X \leq 10^{15}
1 \leq A_i \leq 10^9
入力はすべて整数である

入力

N X
A_1 A_2 \cdots A_N

1 行目には、棚の数 N と商品数の閾値 X がスペース区切りで与えられる。

2 行目には、各棚の商品数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

高橋君が初めて買い物かごを取りに戻る棚の番号を 1 行で出力せよ。そのような棚が存在しない場合は -1 を出力せよ。

入力例 1

5 7
1 2 3 4 5

出力例 1

入力例 2

4 20
3 4 5 6

出力例 2

-1

入力例 3

10 35
2 8 1 7 3 6 9 4 5 10

出力例 3

入力例 4

20 5000000000
120000000 350000000 410000000 275000000 330000000 290000000 480000000 150000000 510000000 220000000 305000000 415000000 390000000 260000000 500000000 340000000 280000000 470000000 360000000 190000000

出力例 4

入力例 5

1 1000000000
1000000000

出力例 5

Score : 300 pts

Problem Statement

Takahashi is shopping at a supermarket.

There are N shelves lined up in a row inside the store, numbered 1, 2, \ldots, N in order from the entrance. The i-th shelf has A_i products displayed on it.

Takahashi looks at the shelves one by one starting from shelf 1 nearest to the entrance, checking the number of products he wants to buy at each shelf. When he finishes checking up to the k-th shelf, if the total number of products from shelves 1 through k, that is A_1 + A_2 + \cdots + A_k, reaches X or more for the first time, he decides to go back to the entrance to get a shopping basket because he can no longer carry everything by hand.

Determine at which shelf number Takahashi finishes checking when he decides to go back to get a shopping basket. If the total does not reach X or more even after checking all shelves up to the N-th shelf, output -1.

Constraints

1 \leq N \leq 5 \times 10^5
1 \leq X \leq 10^{15}
1 \leq A_i \leq 10^9
All input values are integers.

Input

N X
A_1 A_2 \cdots A_N

The first line contains the number of shelves N and the threshold X, separated by a space.

The second line contains the number of products on each shelf A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print in one line the shelf number at which Takahashi first decides to go back to get a shopping basket. If no such shelf exists, print -1.

Sample Input 1

5 7
1 2 3 4 5

Sample Output 1

Sample Input 2

4 20
3 4 5 6

Sample Output 2

-1

Sample Input 3

10 35
2 8 1 7 3 6 9 4 5 10

Sample Output 3

Sample Input 4

20 5000000000
120000000 350000000 410000000 275000000 330000000 290000000 480000000 150000000 510000000 220000000 305000000 415000000 390000000 260000000 500000000 340000000 280000000 470000000 360000000 190000000

Sample Output 4

Sample Input 5

1 1000000000
1000000000

Sample Output 5

C - 花壇の花選び

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は庭に一列に並んだ N 個の花壇を持っています。

各花壇には 1 から N までの番号が付けられており、i 番目の花壇に花を植えると、美しさ A_i が得られます。ただし、隣り合う花壇の両方に花を植えると、根が干渉し合って両方の花が枯れてしまいます。そのため、i 番目の花壇と i+1 番目の花壇の両方に花を植えることはできません（1 \leq i \leq N-1）。

高橋君は、この条件を満たすように花を植える花壇をいくつか選びます。各花壇に花を植えるかどうかは独立に決め、同じ花壇に複数回花を植えることはありません。どの花壇にも花を植えないことも許され、その場合の美しさの合計は 0 とします。

花を植えた花壇から得られる美しさの合計の最大値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
入力はすべて整数

入力

N
A_1 A_2 \ldots A_N

1 行目には、花壇の個数を表す整数 N が与えられる。
2 行目には、各花壇に花を植えたときの美しさを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
A_i は i 番目の花壇に花を植えたときに得られる美しさを表す。

出力

高橋君が達成できる美しさの合計の最大値を 1 行で出力せよ。

入力例 1

5
3 2 5 1 4

出力例 1

入力例 2

8
10 1 10 1 10 1 10 1

出力例 2

入力例 3

15
100 200 300 150 50 400 10 500 250 80 600 30 450 20 350

出力例 3

Score : 366 pts

Problem Statement

Takahashi has N flower beds arranged in a row in his garden.

Each flower bed is numbered from 1 to N. Planting a flower in the i-th flower bed yields a beauty value of A_i. However, if flowers are planted in both of two adjacent flower beds, the roots interfere with each other and both flowers wither. Therefore, it is not allowed to plant flowers in both the i-th and (i+1)-th flower beds (1 \leq i \leq N-1).

Takahashi will select some flower beds to plant flowers in, subject to this condition. The decision of whether to plant a flower in each flower bed is made independently, and no flower bed is planted in more than once. It is also allowed to plant no flowers at all, in which case the total beauty is 0.

Find the maximum possible total beauty obtained from the flower beds in which flowers are planted.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
All inputs are integers

Input

N
A_1 A_2 \ldots A_N

The first line contains an integer N, representing the number of flower beds.
The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the beauty values obtained by planting a flower in each flower bed.
A_i represents the beauty obtained by planting a flower in the i-th flower bed.

Output

Print the maximum total beauty that Takahashi can achieve, in a single line.

Sample Input 1

5
3 2 5 1 4

Sample Output 1

Sample Input 2

8
10 1 10 1 10 1 10 1

Sample Output 2

Sample Input 3

15
100 200 300 150 50 400 10 500 250 80 600 30 450 20 350

Sample Output 3

D - 配達圏内の売上合計

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

ある街には N 軒の店舗がある。街は整数座標の平面で表され、i 番目の店舗は座標 (X_i, Y_i) にあり、その売上は C_i 円である。なお、同じ座標に複数の店舗が存在することもある。

青木君は M 個の配達拠点の候補を考えている。j 番目の候補では、座標 (P_j, Q_j) に拠点を置き、マンハッタン距離で K_j 以下の範囲を配達圏内とする。

すなわち、j 番目の候補の拠点から店舗 i が 配達可能 であるとは、

| X_i - P_j | + | Y_i - Q_j | \le K_j

を満たすことをいう。

各候補について、配達可能な店舗の売上の合計を求めてください。ただし、配達可能な店舗が存在しない場合は 0 を出力してください。

制約

1 \leq N \leq 10^5
1 \leq M \leq 10^5
N + M \leq 1.5 \times 10^5
0 \leq X_i \leq 1000
0 \leq Y_i \leq 1000
1 \leq C_i \leq 10^4
0 \leq P_j \leq 1000
0 \leq Q_j \leq 1000
0 \leq K_j \leq 2000
入力はすべて整数である

入力

N M
X_1 Y_1 C_1
X_2 Y_2 C_2
\vdots
X_N Y_N C_N
P_1 Q_1 K_1
P_2 Q_2 K_2
\vdots
P_M Q_M K_M

1 行目には、店舗の数 N と、配達拠点の候補数 M が、スペース区切りで与えられる。
続く N 行では、各店舗の情報が与えられる。
1 + i 行目には、i 番目の店舗の座標 (X_i, Y_i) と、その売上 C_i が、スペース区切りで与えられる。
続く M 行では、各候補の情報が与えられる。
1 + N + j 行目には、j 番目の候補の拠点座標 (P_j, Q_j) と配達距離の上限 K_j が、スペース区切りで与えられる。

出力

j 行目 (1 \leq j \leq M) に、j 番目の候補で配達可能な店舗の売上の合計を出力せよ。

入力例 1

出力例 1

10
70
90

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

22 10
0 0 5
100 200 7
150 150 9
200 100 11
250 300 13
300 250 15
400 400 17
500 500 19
600 450 21
700 700 23
800 200 25
900 900 27
1000 1000 29
1000 0 31
0 1000 33
450 550 35
550 450 37
350 650 39
650 350 41
200 800 43
800 800 45
500 0 47
0 0 0
1000 1000 0
500 500 100
500 500 1000
250 250 150
750 250 100
0 1000 200
1000 0 500
300 700 200
400 100 250

出力例 4

入力例 5

1 4
1000 1000 9999
1000 1000 0
999 1000 0
0 0 1999
0 0 2000

出力例 5

Score : 400 pts

Problem Statement

A town has N shops. The town is represented as a plane with integer coordinates, where the i-th shop is located at coordinates (X_i, Y_i) and has sales of C_i yen. Note that multiple shops may exist at the same coordinates.

Aoki is considering M candidate locations for a delivery hub. For the j-th candidate, a hub is placed at coordinates (P_j, Q_j), and the delivery range covers all locations within Manhattan distance K_j.

Specifically, shop i is deliverable from the hub of the j-th candidate if and only if:

| X_i - P_j | + | Y_i - Q_j | \le K_j

For each candidate, find the total sales of all deliverable shops. If no shops are deliverable, output 0.

Constraints

1 \leq N \leq 10^5
1 \leq M \leq 10^5
N + M \leq 1.5 \times 10^5
0 \leq X_i \leq 1000
0 \leq Y_i \leq 1000
1 \leq C_i \leq 10^4
0 \leq P_j \leq 1000
0 \leq Q_j \leq 1000
0 \leq K_j \leq 2000
All input values are integers

Input

N M
X_1 Y_1 C_1
X_2 Y_2 C_2
\vdots
X_N Y_N C_N
P_1 Q_1 K_1
P_2 Q_2 K_2
\vdots
P_M Q_M K_M

The first line contains the number of shops N and the number of hub candidates M, separated by a space.
The following N lines give the information for each shop.
The (1 + i)-th line contains the coordinates (X_i, Y_i) of the i-th shop and its sales C_i, separated by spaces.
The following M lines give the information for each candidate.
The (1 + N + j)-th line contains the hub coordinates (P_j, Q_j) and the maximum delivery distance K_j for the j-th candidate, separated by spaces.

Output

On the j-th line (1 \leq j \leq M), output the total sales of the shops deliverable under the j-th candidate.

Sample Input 1

Sample Output 1

10
70
90

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

22 10
0 0 5
100 200 7
150 150 9
200 100 11
250 300 13
300 250 15
400 400 17
500 500 19
600 450 21
700 700 23
800 200 25
900 900 27
1000 1000 29
1000 0 31
0 1000 33
450 550 35
550 450 37
350 650 39
650 350 41
200 800 43
800 800 45
500 0 47
0 0 0
1000 1000 0
500 500 100
500 500 1000
250 250 150
750 250 100
0 1000 200
1000 0 500
300 700 200
400 100 250

Sample Output 4

Sample Input 5

1 4
1000 1000 9999
1000 1000 0
999 1000 0
0 0 1999
0 0 2000

Sample Output 5

E - 気温の安定した期間

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は気象データの分析を行っています。ある地域で N 日間にわたって毎日の最高気温が記録されており、i 日目 (1 \leq i \leq N) の最高気温は H_i ℃です。

高橋君は、この N 日間の記録の中から 連続する K 日以上 の期間であって、気温が 安定している ものを探しています。

ここで、連続する期間（l 日目から r 日目まで、ただし 1 \leq l \leq r \leq N）の気温が「安定している」とは、その期間に含まれる H_l, H_{l+1}, \ldots, H_r の最大値と最小値の差が D 以下であることを意味します。

気温が安定しており、かつ日数（r - l + 1）が K 以上であるような連続する期間のうち、日数が最大となるものの日数を求めてください。そのような期間が存在しない場合は -1 を出力してください。

制約

1 \leq N \leq 5 \times 10^5
1 \leq K \leq N
0 \leq D \leq 10^9
-10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数である

入力

N K D
H_1 H_2 \ldots H_N

1 行目には、記録の日数を表す整数 N、期間に必要な最小日数を表す整数 K、許容される気温差（℃）を表す整数 D が、スペース区切りで与えられる。
2 行目には、各日の最高気温（℃）を表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

気温が安定しており、かつ日数が K 以上であるような連続する期間が存在する場合は、その最大日数を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

7 3 2
10 11 10 12 15 14 13

出力例 1

入力例 2

5 3 1
1 3 1 3 1

出力例 2

-1

入力例 3

15 4 5
3 5 7 4 6 8 20 22 25 21 23 24 22 21 30

出力例 3

入力例 4

30 5 3
1 2 3 4 100 10 11 12 13 12 11 10 11 12 13 200 50 51 52 53 51 50 52 53 51 50 300 400 500 600

出力例 4

入力例 5

1 1 0
42

出力例 5

Score : 466 pts

Problem Statement

Takahashi is analyzing weather data. The daily maximum temperatures have been recorded over N days in a certain region, and the maximum temperature on day i (1 \leq i \leq N) is H_i ℃.

Takahashi is looking for a period of at least K consecutive days within these N days of records where the temperature is stable.

Here, the temperature in a consecutive period (from day l to day r, where 1 \leq l \leq r \leq N) is said to be "stable" if the difference between the maximum value and the minimum value among H_l, H_{l+1}, \ldots, H_r is at most D.

Among all consecutive periods where the temperature is stable and the number of days (r - l + 1) is at least K, find the maximum number of days. If no such period exists, output -1.

Constraints

1 \leq N \leq 5 \times 10^5
1 \leq K \leq N
0 \leq D \leq 10^9
-10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
All input values are integers

Input

N K D
H_1 H_2 \ldots H_N

The first line contains an integer N representing the number of recorded days, an integer K representing the minimum number of days required for a period, and an integer D representing the allowable temperature difference (℃), separated by spaces.
The second line contains integers H_1, H_2, \ldots, H_N representing the maximum temperature (℃) on each day, separated by spaces.

Output

If there exists a consecutive period where the temperature is stable and the number of days is at least K, output the maximum number of days in one line. If no such period exists, output -1 in one line.

Sample Input 1

7 3 2
10 11 10 12 15 14 13

Sample Output 1

Sample Input 2

5 3 1
1 3 1 3 1

Sample Output 2

-1

Sample Input 3

15 4 5
3 5 7 4 6 8 20 22 25 21 23 24 22 21 30

Sample Output 3

Sample Input 4

30 5 3
1 2 3 4 100 10 11 12 13 12 11 10 11 12 13 200 50 51 52 53 51 50 52 53 51 50 300 400 500 600

Sample Output 4

Sample Input 5

1 1 0
42