AtCoder Weekday Contest 0114 Beta

A - 照明の範囲

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

配点 : 266 点

問題文

高橋君は、直線状の道路に設置された街灯の管理をしています。

道路は数直線として表され、街灯は原点の位置に設置されています。道路上には N 個の標識があり、i 番目の標識は座標 X_i の位置にあり、重要度 P_i を持っています。なお、同じ座標に複数の標識が存在することもあります。

高橋君は、街灯の照らす範囲を決める非負整数 R を 1 つ選びます。R を選ぶと、街灯は原点からの距離が R 以下の範囲、すなわち座標 -R 以上 R 以下の範囲を照らします。このとき、|X_i| \leq R を満たすすべての標識が照らされます。

一方、照明の電力コストとして R^2 がかかります。

照らされた標識の重要度の合計値から電力コスト R^2 を引いた値を「効果」と呼びます。すなわち、R を選んだときの効果は次のように定義されます。

\left(\sum_{|X_i| \leq R} P_i\right) - R^2

R = 0 を選んだ場合、電力コストは 0 であり、照らされるのは座標 0 にある標識のみです。座標 0 に標識が存在すれば効果はその重要度の合計（正の値）となり、存在しなければ効果は 0 となります。したがって、効果の最大値は常に 0 以上です。

高橋君が非負整数 R を最適に選んだとき、効果の最大値を求めてください。

制約

1 \leq N \leq 100
-100 \leq X_i \leq 100
1 \leq P_i \leq 100
X_i および P_i はすべて整数である

入力

N
X_1 P_1
X_2 P_2
\vdots
X_N P_N

1 行目には、標識の数を表す整数 N が与えられる。
続く N 行のうち i 行目には、i 番目の標識の座標 X_i と重要度 P_i がスペース区切りで与えられる。

出力

効果の最大値を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

2
50 1
-50 1

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

1
0 1

出力例 5

Score : 266 pts

Problem Statement

Takahashi manages streetlights installed along a straight road.

The road is represented as a number line, and a streetlight is installed at the origin. There are N signs on the road, where the i-th sign is located at coordinate X_i and has an importance of P_i. Note that multiple signs may exist at the same coordinate.

Takahashi chooses a single non-negative integer R that determines the range illuminated by the streetlight. When R is chosen, the streetlight illuminates the range within distance R from the origin, that is, the range from coordinate -R to coordinate R inclusive. At this time, all signs satisfying |X_i| \leq R are illuminated.

On the other hand, the electrical power cost of the illumination is R^2.

The value obtained by subtracting the power cost R^2 from the total importance of the illuminated signs is called the "effectiveness." That is, the effectiveness when R is chosen is defined as follows:

\left(\sum_{|X_i| \leq R} P_i\right) - R^2

When R = 0 is chosen, the power cost is 0, and only signs at coordinate 0 are illuminated. If there are signs at coordinate 0, the effectiveness equals the sum of their importances (a positive value); otherwise, the effectiveness is 0. Therefore, the maximum effectiveness is always at least 0.

Find the maximum value of the effectiveness when Takahashi optimally chooses a non-negative integer R.

Constraints

1 \leq N \leq 100
-100 \leq X_i \leq 100
1 \leq P_i \leq 100
X_i and P_i are all integers.

Input

N
X_1 P_1
X_2 P_2
\vdots
X_N P_N

The first line contains an integer N representing the number of signs.
The i-th of the following N lines contains the coordinate X_i and importance P_i of the i-th sign, separated by a space.

Output

Output the maximum value of the effectiveness in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

2
50 1
-50 1

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

1
0 1

Sample Output 5

B - ペアを見つけよう

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

配点 : 300 点

問題文

高橋君は N 人の生徒が受けたテストの点数を管理しています。青木先生から「自分以外の生徒の中に、点数の差の絶対値がちょうど K である相手がいる生徒は何人いるか数えてほしい」と頼まれました。

N 人の生徒にはそれぞれ 1 から N までの番号がついており、生徒 i のテストの点数は A_i 点です（A_i は 0 以上の整数）。なお、同じ点数の生徒が複数いることもあります。

生徒 i が「条件を満たす生徒」であるとは、次を満たす生徒 j（1 \le j \le N, j \neq i）が少なくとも 1 人存在することを言います。

|A_i - A_j| = K

すなわち、生徒 i と生徒 j の点数の差の絶対値がちょうど K であるような、自分とは異なる生徒 j が存在すればよいです。

例えば K = 0 の場合、生徒 i が条件を満たすのは、自分と同じ点数の別の生徒（i とは異なる番号の生徒）が少なくとも 1 人存在するときです。

条件を満たす生徒の人数を求めてください。条件を満たすペアの組数ではなく、条件を満たす生徒が全部で何人いるかを答えることに注意してください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq K \leq 10^9
0 \leq A_i \leq 10^9（1 \leq i \leq N）
入力はすべて整数である。

入力

N K
A_1 A_2 \dots A_N

1 行目には、生徒の人数を表す整数 N と、点数の差の条件を表す非負整数 K が、スペース区切りで与えられる。
2 行目には、各生徒のテストの点数を表す整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。

出力

条件を満たす生徒の人数を 1 行で出力せよ。

入力例 1

5 2
1 3 5 7 2

出力例 1

入力例 2

4 10
1 2 3 4

出力例 2

入力例 3

10 0
5 5 3 3 3 7 7 1 2 4

出力例 3

入力例 4

15 5
10 15 20 25 30 35 40 3 8 13 18 23 28 33 38

出力例 4

入力例 5

1 0
1000000000

出力例 5

Score : 300 pts

Problem Statement

Takahashi is managing the test scores of N students. Teacher Aoki has asked him: "How many students have at least one other student whose score differs from theirs by exactly K?"

The N students are numbered from 1 to N, and student i has a test score of A_i points (A_i is a non-negative integer). Note that multiple students may have the same score.

Student i is said to be a "student satisfying the condition" if there exists at least one student j (1 \le j \le N, j \neq i) such that:

|A_i - A_j| = K

In other words, there must exist a student j different from student i such that the absolute difference between the scores of student i and student j is exactly K.

For example, when K = 0, student i satisfies the condition if and only if there exists at least one other student (with a different index from i) who has the same score.

Find the number of students who satisfy the condition. Note that you should output the total number of students satisfying the condition, not the number of pairs that satisfy the condition.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq K \leq 10^9
0 \leq A_i \leq 10^9 (1 \leq i \leq N)
All input values are integers.

Input

N K
A_1 A_2 \dots A_N

The first line contains an integer N representing the number of students and a non-negative integer K representing the score difference condition, separated by a space.
The second line contains integers A_1, A_2, \dots, A_N representing the test scores of each student, separated by spaces.

Output

Output the number of students satisfying the condition in a single line.

Sample Input 1

5 2
1 3 5 7 2

Sample Output 1

Sample Input 2

4 10
1 2 3 4

Sample Output 2

Sample Input 3

10 0
5 5 3 3 3 7 7 1 2 4

Sample Output 3

Sample Input 4

15 5
10 15 20 25 30 35 40 3 8 13 18 23 28 33 38

Sample Output 4

Sample Input 5

1 0
1000000000

Sample Output 5

C - 宝箱回収

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

配点 : 366 点

問題文

高橋君はダンジョンの探索をしています。

ダンジョンには一直線の通路があり、数直線上の N 個の異なる位置に宝箱が置かれています。i 番目の宝箱は座標 X_i にあり、C_i 枚のコインが入っています。

高橋君は魔法の杖を持っており、j = 1, 2, \ldots, M の順に合計 M 回この杖を振ります。j 回目に杖を振ると、座標が L_j 以上 R_j 以下の範囲にある宝箱のうち、まだ空になっていないものすべてから、中に入っているコインをすべて回収します。コインを回収された宝箱は空になり、それ以降に杖を振った際にその宝箱が範囲に含まれていても、コインは得られません。

M 回すべて杖を振り終わった後に、高橋君が回収したコインの合計枚数を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq X_i \leq 10^9
すべての宝箱の座標は互いに異なる（i \neq k ならば X_i \neq X_k）
1 \leq C_i \leq 10^9
1 \leq L_j \leq R_j \leq 10^9
入力はすべて整数
答えは 2^{63} - 1 以下であることが保証される（64ビット符号付き整数に収まる）

入力

N M
X_1 C_1
X_2 C_2
\vdots
X_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

1 行目には、宝箱の個数 N と杖を振る回数 M が、スペース区切りで与えられる。
続く N 行では、各宝箱の情報が与えられる。
このうち i 行目では、i 番目の宝箱の座標 X_i と入っているコインの枚数 C_i が、スペース区切りで与えられる。
続く M 行では、杖を振るたびの範囲が与えられる。
このうち j 行目では、j 回目に杖を振るときの範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

回収したコインの合計枚数を 1 行で出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

8 5
1 10
3 50
5 100
8 200
12 300
20 400
25 500
1000000000 999999999
1 5
1 5
10 15
7 25
999999999 1000000000

出力例 3

1000001559

Score : 366 pts

Problem Statement

Takahashi is exploring a dungeon.

The dungeon has a straight corridor, and there are treasure chests placed at N distinct positions on a number line. The i-th treasure chest is located at coordinate X_i and contains C_i coins.

Takahashi has a magic wand, and he waves it a total of M times, in order j = 1, 2, \ldots, M. When he waves the wand for the j-th time, he collects all the coins from every treasure chest that is located at a coordinate between L_j and R_j (inclusive) and has not yet been emptied. A treasure chest from which coins have been collected becomes empty, and even if that treasure chest falls within the range of a subsequent wand wave, no coins will be obtained from it.

Determine the total number of coins Takahashi has collected after all M waves of the wand.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq X_i \leq 10^9
All treasure chest coordinates are distinct (X_i \neq X_k if i \neq k)
1 \leq C_i \leq 10^9
1 \leq L_j \leq R_j \leq 10^9
All input values are integers
It is guaranteed that the answer is at most 2^{63} - 1 (fits in a 64-bit signed integer)

Input

N M
X_1 C_1
X_2 C_2
\vdots
X_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

The first line contains the number of treasure chests N and the number of wand waves M, separated by a space.
The following N lines give the information for each treasure chest.
The i-th of these lines contains the coordinate X_i of the i-th treasure chest and the number of coins C_i it contains, separated by a space.
The following M lines give the range for each wand wave.
The j-th of these lines contains the left endpoint L_j and right endpoint R_j of the range for the j-th wand wave, separated by a space.

Output

Print the total number of collected coins on a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

8 5
1 10
3 50
5 100
8 200
12 300
20 400
25 500
1000000000 999999999
1 5
1 5
10 15
7 25
999999999 1000000000

Sample Output 3

1000001559

D - 避難所の配置

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

配点 : 400 点

問題文

高橋君は、ある直線状の道路に沿って K 個の避難所を設置する計画を立てています。道路は数直線として表され、 N 個の集落が数直線上の相異なる整数座標 X_1, X_2, \ldots, X_N にそれぞれ位置しています。

高橋君は、ちょうど K 個の避難所をこの数直線上に設置します。避難所は整数座標に限らず任意の実数座標に設置でき、集落と同じ座標にも設置できます。ただし、異なる 2 つの避難所を同じ座標に設置することはできません。

各集落の住民は、自分の集落から最も近い避難所へ避難します。最も近い避難所が複数ある場合は、そのうち座標が最も小さいものへ避難するものとします。

ある避難所の 受入数 とは、その避難所を避難先とする集落の個数として定義されます。高橋君は、すべての避難所の受入数が 1 以上となるように避難所を配置しなければなりません。すなわち、どの避難所にも少なくとも 1 つの集落が避難先として割り当てられている必要があります。これは、避難所を無駄な位置に配置して実質的に使わないことを防ぐための条件です。K \leq N であるため、この条件を満たす配置は必ず存在します。

この条件を満たす避難所の配置のうち、各集落からその避難先の避難所までの距離の最大値 を最小化したいです。この最大値の最小値を d とします。

d は 0 以上であり、整数または半整数（整数に \frac{1}{2} を加えた値）のいずれかになることが証明できます。したがって 2d は必ず非負整数となります。2d の値を整数として出力してください。

制約

1 \leq K \leq N \leq 2 \times 10^5
0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
入力はすべて整数である

入力

N K
X_1 X_2 \ldots X_N

1 行目には、集落の数を表す整数 N と、設置する避難所の数を表す整数 K が、スペース区切りで与えられる。
2 行目には、各集落の座標を表す整数 X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。

出力

すべての避難所の受入数が 1 以上となる配置のうち、各集落からその避難先の避難所までの距離の最大値として達成可能な最小値を d とする。2d の値を整数として 1 行で出力せよ。

入力例 1

5 2
0 2 3 10 12

出力例 1

入力例 2

4 4
1 5 9 20

出力例 2

入力例 3

12 4
0 3 4 8 15 16 23 42 43 44 60 75

出力例 3

入力例 4

30 7
0 1 2 10 11 20 35 36 37 50 51 52 80 100 101 150 151 152 153 200 260 261 300 301 302 400 500 700 701 900

出力例 4

入力例 5

1 1
1000000000

出力例 5

Score : 400 pts

Problem Statement

Takahashi is planning to place K shelters along a straight road. The road is represented as a number line, and N villages are located at distinct integer coordinates X_1, X_2, \ldots, X_N on the number line.

Takahashi will place exactly K shelters on this number line. Shelters can be placed at any real-valued coordinate, not limited to integers, and can be placed at the same coordinate as a village. However, two different shelters cannot be placed at the same coordinate.

The residents of each village will evacuate to the nearest shelter from their village. If there are multiple nearest shelters, they will evacuate to the one with the smallest coordinate.

The acceptance count of a shelter is defined as the number of villages assigned to that shelter as their evacuation destination. Takahashi must place the shelters such that the acceptance count of every shelter is at least 1. In other words, every shelter must have at least one village assigned to it as an evacuation destination. This condition prevents placing shelters at wasteful positions where they are effectively unused. Since K \leq N, a placement satisfying this condition always exists.

Among all shelter placements satisfying this condition, we want to minimize the maximum distance from each village to its assigned shelter. Let d be the minimum value of this maximum distance.

It can be proven that d is non-negative and is either an integer or a half-integer (an integer plus \frac{1}{2}). Therefore, 2d is always a non-negative integer. Output the value of 2d as an integer.

Constraints

1 \leq K \leq N \leq 2 \times 10^5
0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
All inputs are integers

Input

N K
X_1 X_2 \ldots X_N

The first line contains an integer N representing the number of villages and an integer K representing the number of shelters to place, separated by a space.
The second line contains integers X_1, X_2, \ldots, X_N representing the coordinates of each village, separated by spaces.

Output

Among all placements where every shelter has an acceptance count of at least 1, let d be the minimum achievable value of the maximum distance from each village to its assigned shelter. Output the value of 2d as an integer on a single line.

Sample Input 1

5 2
0 2 3 10 12

Sample Output 1

Sample Input 2

4 4
1 5 9 20

Sample Output 2

Sample Input 3

12 4
0 3 4 8 15 16 23 42 43 44 60 75

Sample Output 3

Sample Input 4

30 7
0 1 2 10 11 20 35 36 37 50 51 52 80 100 101 150 151 152 153 200 260 261 300 301 302 400 500 700 701 900

Sample Output 4

Sample Input 5

1 1
1000000000

Sample Output 5

E - 広告キャンペーンの選択

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

配点 : 466 点

問題文

高橋君は、あるオンラインショップのマーケティング担当者です。このショップでは N 種類の商品を販売しており、商品 i の利益は V_i 円です。

高橋君は広告キャンペーンを実施する計画を立てています。利用可能な広告キャンペーンは M 種類あり、各キャンペーン j は商品 L_j から商品 R_j までの連続した商品（商品 L_j, L_j+1, \ldots, R_j）を宣伝対象としています。

キャンペーンを実施すると、その宣伝対象となっている商品がすべて売れます。同じ商品が複数のキャンペーンで宣伝されていても問題ありませんが、その商品の利益は 1 回だけ合計に加算されます。

高橋君は予算の都合上、ちょうど K 種類のキャンペーンを選んで実施することにしました。

K 種類のキャンペーンを選んで実施したとき、売れる商品から得られる利益の合計の最大値を求めてください。

制約

1 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq K \leq \min(M, 10)
1 \leq V_i \leq 10^9 (1 \leq i \leq N)
1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
入力はすべて整数

入力

N M K
V_1 V_2 \ldots V_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

1 行目には、商品の種類数 N 、キャンペーンの種類数 M 、実施するキャンペーンの数 K が、スペース区切りで与えられる。
2 行目には、各商品の利益 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
3 行目から M 行では、各キャンペーンが宣伝対象とする商品の範囲が与えられる。
2 + j 行目では、キャンペーン j が宣伝対象とする商品の範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

K 種類のキャンペーンを選んで実施したとき、売れる商品から得られる利益の合計の最大値を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

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

出力例 2

入力例 3

12 10 3
5 9 2 6 4 8 3 7 10 1 11 12
1 4
3 6
5 8
7 10
9 12
2 9
1 12
4 4
6 11
2 3

出力例 3

入力例 4

25 22 7
4 15 8 23 16 42 7 31 5 18 27 11 36 9 14 22 6 40 3 29 12 34 20 10 25
1 5
6 10
11 15
16 20
21 25
1 10
5 15
10 20
15 25
3 8
7 13
12 18
18 25
2 22
4 4
9 9
14 17
19 23
1 25
6 6
8 21
11 24

出力例 4

入力例 5

1 1 1
1000000000
1 1

出力例 5

1000000000

入力例 6

30 25 3
5 12 7 20 3 15 8 30 2 25 11 6 18 4 22 9 14 1 27 10 16 13 24 19 21 17 23 26 28 29
1 5
3 10
6 12
11 15
14 20
19 25
14 21
22 24
5 5
10 10
15 15
20 20
25 25
2 8
7 13
13 17
21 27
4 11
9 14
12 19
1 1
30 30
22 24
15 19
3 8

出力例 6

Score : 466 pts

Problem Statement

Takahashi is a marketing manager for an online shop. The shop sells N types of products, and the profit of product i is V_i yen.

Takahashi is planning to run advertising campaigns. There are M types of available advertising campaigns, and each campaign j targets a consecutive range of products from product L_j to product R_j (products L_j, L_j+1, \ldots, R_j).

When a campaign is run, all products targeted by that campaign are sold. It is fine for the same product to be targeted by multiple campaigns, but the profit from that product is added to the total only once.

Due to budget constraints, Takahashi has decided to select and run exactly K campaigns.

Find the maximum total profit obtainable from the products sold when exactly K campaigns are selected and run.

Constraints

1 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq K \leq \min(M, 10)
1 \leq V_i \leq 10^9 (1 \leq i \leq N)
1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
All inputs are integers

Input

N M K
V_1 V_2 \ldots V_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

The first line contains the number of product types N, the number of campaign types M, and the number of campaigns to run K, separated by spaces.
The second line contains the profit of each product V_1, V_2, \ldots, V_N, separated by spaces.
From the 3rd line to the next M lines, the range of products targeted by each campaign is given.
The (2 + j)-th line contains the left endpoint L_j and right endpoint R_j of the range of products targeted by campaign j, separated by spaces.

Output

Print in one line the maximum total profit obtainable from the products sold when exactly K campaigns are selected and run.

Sample Input 1

Sample Output 1

Sample Input 2

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

Sample Output 2

Sample Input 3

12 10 3
5 9 2 6 4 8 3 7 10 1 11 12
1 4
3 6
5 8
7 10
9 12
2 9
1 12
4 4
6 11
2 3

Sample Output 3

Sample Input 4

25 22 7
4 15 8 23 16 42 7 31 5 18 27 11 36 9 14 22 6 40 3 29 12 34 20 10 25
1 5
6 10
11 15
16 20
21 25
1 10
5 15
10 20
15 25
3 8
7 13
12 18
18 25
2 22
4 4
9 9
14 17
19 23
1 25
6 6
8 21
11 24

Sample Output 4

Sample Input 5

1 1 1
1000000000
1 1

Sample Output 5

1000000000

Sample Input 6

30 25 3
5 12 7 20 3 15 8 30 2 25 11 6 18 4 22 9 14 1 27 10 16 13 24 19 21 17 23 26 28 29
1 5
3 10
6 12
11 15
14 20
19 25
14 21
22 24
5 5
10 10
15 15
20 20
25 25
2 8
7 13
13 17
21 27
4 11
9 14
12 19
1 1
30 30
22 24
15 19
3 8