Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
とある銭湯には、スイッチを押すと T 秒間お湯が出るシャワーがあります。
なお、お湯が出ているときにスイッチを押すと、そのタイミングから T 秒間お湯が出つづけます。 お湯の出る時間が T 秒間延長されるわけではないことに注意してください。
このシャワーの前を、N 人の人がスイッチを押して通り過ぎていきます。 i 人目の人は、1 人目の人がスイッチを押した t_i 秒後にスイッチを押します。
お湯が出る時間の総和は何秒かを求めてください。
制約
- 1 ≦ N ≦ 200,000
- 1 ≦ T ≦ 10^9
- 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≦ 10^9
- T, t_i はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N T t_1 t_2 ... t_N
出力
お湯が出る時間の総和を X 秒として、X を出力する。
入力例 1
2 4 0 3
出力例 1
7
1 人目の人がスイッチを押し、お湯が 3 秒出た後にもう一度スイッチが押され、4 秒間お湯が出続けます。 よって合計で 7 秒間お湯が出ます。
入力例 2
2 4 0 5
出力例 2
8
1 人目の人がスイッチを押して、お湯が出終わった 1 秒後にもう一度スイッチが押されます。
入力例 3
4 1000000000 0 1000 1000000 1000000000
出力例 3
2000000000
入力例 4
1 1 0
出力例 4
1
入力例 5
9 10 0 3 5 7 100 110 200 300 311
出力例 5
67
Score : 300 points
Problem Statement
In a public bath, there is a shower which emits water for T seconds when the switch is pushed.
If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds. Note that it does not mean that the shower emits water for T additional seconds.
N people will push the switch while passing by the shower. The i-th person will push the switch t_i seconds after the first person pushes it.
How long will the shower emit water in total?
Constraints
- 1 ≤ N ≤ 200,000
- 1 ≤ T ≤ 10^9
- 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9
- T and each t_i are integers.
Input
Input is given from Standard Input in the following format:
N T t_1 t_2 ... t_N
Output
Assume that the shower will emit water for a total of X seconds. Print X.
Sample Input 1
2 4 0 3
Sample Output 1
7
Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.
Sample Input 2
2 4 0 5
Sample Output 2
8
One second after the shower stops emission of water triggered by the first person, the switch is pushed again.
Sample Input 3
4 1000000000 0 1000 1000000 1000000000
Sample Output 3
2000000000
Sample Input 4
1 1 0
Sample Output 4
1
Sample Input 5
9 10 0 3 5 7 100 110 200 300 311
Sample Output 5
67
Time Limit: 2 sec / Memory Limit: 256 MB
Score : 400 points
Problem Statement
You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.
You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.
Your objective is to maximize the total value of the selected items.
Constraints
- 1 ≤ N ≤ 100
- 1 ≤ W ≤ 10^9
- 1 ≤ w_i ≤ 10^9
- For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.
- 1 ≤ v_i ≤ 10^7
- W, each w_i and v_i are integers.
Input
Input is given from Standard Input in the following format:
N W w_1 v_1 w_2 v_2 : w_N v_N
Output
Print the maximum possible total value of the selected items.
Sample Input 1
4 6 2 1 3 4 4 10 3 4
Sample Output 1
11
The first and third items should be selected.
Sample Input 2
4 6 2 1 3 7 4 10 3 6
Sample Output 2
13
The second and fourth items should be selected.
Sample Input 3
4 10 1 100 1 100 1 100 1 100
Sample Output 3
400
You can take everything.
Sample Input 4
4 1 10 100 10 100 10 100 10 100
Sample Output 4
0
You can take nothing.
配点 : 400 点
問題文
あなたは N 個の物と、強度 W のバッグを持っています。 i 個目の物は、重さが w_i で価値が v_i です。
あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は W 以下でなくてはいけません。
あなたは、バッグに入れた物の価値の総和を最大化したいです。
制約
- 1 ≦ N ≦ 100
- 1 ≦ W ≦ 10^9
- 1 ≦ w_i ≦ 10^9
- すべての i = 2,3,...,N について、w_1 ≦ w_i ≦ w_1 + 3
- 1 ≦ v_i ≦ 10^7
- W, w_i, v_i はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N W w_1 v_1 w_2 v_2 : w_N v_N
出力
価値の総和の最大値を出力する。
入力例 1
4 6 2 1 3 4 4 10 3 4
出力例 1
11
1, 3 個目の物を選ぶと良いです。
入力例 2
4 6 2 1 3 7 4 10 3 6
出力例 2
13
2, 4 個目の物を選ぶと良いです。
入力例 3
4 10 1 100 1 100 1 100 1 100
出力例 3
400
すべての物が選べます。
入力例 4
4 1 10 100 10 100 10 100 10 100
出力例 4
0
1 個も物が選べません。
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
2 個の白いボールが入った袋が N 個あります。i 個目の袋にはそれぞれ整数 x_i と y_i が書かれたボールが 1 個ずつ入っています。
あなたはこの袋それぞれについて、片方のボールを赤く塗り、もう片方を青く塗ります。
そのあと 2N 個のボールを、塗られた色で分類します。
そして
- 赤く塗られたボールに書かれた整数の最大値を R_{max}
- 赤く塗られたボールに書かれた整数の最小値を R_{min}
- 青く塗られたボールに書かれた整数の最大値を B_{max}
- 青く塗られたボールに書かれた整数の最小値を B_{min}
としたときに、(R_{max} - R_{min}) \times (B_{max} - B_{min}) の最小値を求めてください。
制約
- 1 ≦ N ≦ 200,000
- 1 ≦ x_i, y_i ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 : x_N y_N
出力
問題の答えを出力する。
入力例 1
3 1 2 3 4 5 6
出力例 1
15
x_1, x_2, y_3 の書かれたボールを赤色に塗り、 y_1, y_2, x_3 の書かれたボールを青色に塗ると最適解になります。
入力例 2
3 1010 10 1000 1 20 1020
出力例 2
380
入力例 3
2 1 1 1000000000 1000000000
出力例 3
999999998000000001
Score : 700 points
Problem Statement
There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.
For each of these bags, you will paint one of the balls red, and paint the other blue.
Afterwards, the 2N balls will be classified according to color.
Then, we will define the following:
- R_{max}: the maximum integer written on a ball painted in red
- R_{min}: the minimum integer written on a ball painted in red
- B_{max}: the maximum integer written on a ball painted in blue
- B_{min}: the minimum integer written on a ball painted in blue
Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).
Constraints
- 1 ≤ N ≤ 200,000
- 1 ≤ x_i, y_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 : x_N y_N
Output
Print the minimum possible value.
Sample Input 1
3 1 2 3 4 5 6
Sample Output 1
15
The optimal solution is to paint the balls with x_1, x_2, y_3 red, and paint the balls with y_1, y_2, x_3 blue.
Sample Input 2
3 1010 10 1000 1 20 1020
Sample Output 2
380
Sample Input 3
2 1 1 1000000000 1000000000
Sample Output 3
999999998000000001
Time Limit: 2 sec / Memory Limit: 256 MB
Score : 900 points
Problem Statement
There are N squares in a row. The squares are numbered 1, 2, ..., N from left to right.
You have two pieces, initially placed on square A and B, respectively. You will be asked to process Q queries of the following kind, in the order received:
- Given an integer x_i, move one of the two pieces of your choice to square x_i.
Here, it takes you one second to move a piece one square. That is, the time it takes to move a piece from square X to Y is |X-Y| seconds.
Your objective is to process all the queries in the shortest possible time.
You may only move the pieces in response to queries, and you may not move both pieces at the same time. Also, it is not allowed to rearrange the order in which queries are given. It is, however, allowed to have both pieces in the same square at the same time.
Constraints
- 1 ≤ N, Q ≤ 200,000
- 1 ≤ A, B ≤ N
- 1 ≤ x_i ≤ N
Input
Input is given from Standard Input in the following format:
N Q A B x_1 x_2 ... x_Q
Output
Let the shortest possible time to process all the queries be X seconds. Print X.
Sample Input 1
8 3 1 8 3 5 1
Sample Output 1
7
All the queries can be processed in seven seconds, by:
- moving the piece at square 1 to 3
- moving the piece at square 8 to 5
- moving the piece at square 3 to 1
Sample Input 2
9 2 1 9 5 1
Sample Output 2
4
The piece at square 9 should be moved first.
Sample Input 3
9 2 1 9 5 9
Sample Output 3
4
The piece at square 1 should be moved first.
Sample Input 4
11 16 8 1 1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7
Sample Output 4
21
配点 : 900 点
問題文
N 個のマスが一列に並んでいます。マスには順に 1, 2, ..., N と番号を振ってあるものとします。
あなたはコマを 2 つ持っており、最初の時点ではマス A, B においてあります。
以下のクエリがQ 個与えられるので、順番に処理します。
- x_i が与えられる。2 つのコマのどちらかをマス x_i に移動させる。どちらを移動させるかは好きに選んで良い。
ただし、コマは 1 マス分動くのに 1 秒の時間を必要とします。 つまり、マス X のコマをマス Y に動かすには |X-Y| 秒必要です。
あなたの目的は、出来る限り速く全てのクエリを処理することです。
なお、クエリ以外でのコマの移動は許されません。 また、クエリの順番を並び替えたり、コマを 2 個同時に動かしたりすることも許されません。 ただし、2 個のコマが同時に同じマスにいることは許されます。
制約
- 1 ≦ N, Q ≦ 200,000
- 1 ≦ A, B ≦ N
- 1 ≦ x_i ≦ N
入力
入力は以下の形式で標準入力から与えられる。
N Q A B x_1 x_2 ... x_Q
出力
全てのクエリを処理するのにかかる最小の時間を X 秒として、X を出力する。
入力例 1
8 3 1 8 3 5 1
出力例 1
7
- マス 1 のコマをマス 3 に動かす
- マス 8 のコマをマス 5 に動かす
- マス 3 のコマをマス 1 に動かす
この通りにコマを動かすと 7 秒で全てのクエリを処理できます。
入力例 2
9 2 1 9 5 1
出力例 2
4
最初に動かすべきはマス 9 のコマです。
入力例 3
9 2 1 9 5 9
出力例 3
4
最初に動かすべきはマス 1 のコマです。
入力例 4
11 16 8 1 1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7
出力例 4
21