実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の巨人がいます。巨人にはそれぞれ 1, 2, \ldots, N の名前がついており、巨人 i が地面に立ったとき、肩の高さは A_i、頭の高さは B_i となります。
あなたは (1, 2, \ldots, N) を並べ替えて得られる数列 (P_1, P_2, \ldots, P_N) を選び、以下の規則に従って N 人の巨人を積み上げることができます。
-
まず地面に巨人 P_1 を立たせる。巨人 P_1 の肩は地面を基準として A_{P_1}、頭は地面を基準として B_{P_1} の高さとなる。
-
i = 1, 2, \ldots, N - 1 の順に巨人 P_i の肩の上に巨人 P_{i + 1} を立たせる。巨人 P_i の肩が地面を基準として高さ t のとき、巨人 P_{i + 1} の肩は地面を基準として t + A_{P_{i + 1}}、頭は地面を基準として t + B_{P_{i + 1}} の高さとなる。
一番上に立っている巨人、すなわち巨人 P_N の地面を基準とした頭の高さとして実現できる最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 4 10 5 8 2 9
出力例 1
18
(P_1, P_2, P_3) = (2, 1, 3) とすると、地面を基準として巨人 2 は肩の高さが 5、頭の高さが 8、巨人 1 は肩の高さが 9、頭の高さが 15、巨人 3 は肩の高さが 11、頭の高さが 18 となります。
一番上に立っている巨人の頭の高さが地面を基準として 18 より大きくなることはないため 18 を出力します。
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
5
入力例 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
出力例 3
7362669937
Score: 300 points
Problem Statement
There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.
You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:
-
First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.
-
For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.
Find the maximum possible height of the head of the topmost giant P_N from the ground.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 4 10 5 8 2 9
Sample Output 1
18
If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.
The head height of the topmost giant from the ground cannot be greater than 18, so print 18.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
Sample Output 3
7362669937
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
1 個の 0 のみからなる数列 A=(0) があります。
また、L と R のみからなる長さ N の文字列 S=s_1s_2\ldots s_N が与えられます。
i=1,2,\ldots ,N の順番で、次の操作を行います。
- s_i が
Lのとき、A 内にある i-1 のすぐ左に i を挿入する - s_i が
Rのとき、A 内にある i-1 のすぐ右に i を挿入する
最終的な A を求めてください。
制約
- 1\leq N \leq 5\times 10^5
- N は整数である
- |S| = N
- s_i は
LかRのいずれかである
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
最終的な A を空白区切りで出力せよ。
入力例 1
5 LRRLR
出力例 1
1 2 4 5 3 0
はじめ、A=(0) です。
s_1 が L なので、A=(1,0) となります。
s_2 が R なので、A=(1,2,0) となります。
s_3 が R なので、A=(1,2,3,0) となります。
s_4 が L なので、A=(1,2,4,3,0) となります。
s_5 が R なので、A=(1,2,4,5,3,0) となります。
入力例 2
7 LLLLLLL
出力例 2
7 6 5 4 3 2 1 0
Score : 400 points
Problem Statement
There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.
For each i=1, 2, \ldots, N in this order, the following will be done.
- If s_i is
L, insert i to the immediate left of i-1 in A. - If s_i is
R, insert i to the immediate right of i-1 in A.
Find the final contents of A.
Constraints
- 1\leq N \leq 5\times 10^5
- N is an integer.
- |S| = N
- s_i is
LorR.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the final contents of A, separated by spaces.
Sample Input 1
5 LRRLR
Sample Output 1
1 2 4 5 3 0
Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).
Sample Input 2
7 LLLLLLL
Sample Output 2
7 6 5 4 3 2 1 0
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
N 個のボールが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のボールは色 C_i で、価値は V_i です。
高橋君はこの列から ちょうど K 個のボールを取り除いたうえで、 残ったボールを元の順番で並べたときに同じ色のボールが隣り合わないようにしたいと考えています。 また、その条件のもとで、列に残ったボールの価値の総和をなるべく大きくしたいと考えています。
高橋君が、残ったボールの列において同じ色のボールが隣り合わないように K 個のボールを取り除くことができるか判定し、 できる場合は列に残ったボールの価値の総和としてあり得る最大の値を求めてください。
制約
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
出力
高橋君が同じ色のボールが隣り合わないようにK 個のボールを取り除くことができる場合は、 列に残ったボールの価値の総和としてあり得る最大値を整数で出力せよ。 できない場合は、-1 を出力せよ。
入力例 1
5 2 1 1 3 5 3 3 1 4 1 2
出力例 1
10
左から、3,5 番目のボールを取り除くと、残ったボールは左から順に色 1,3,1 であるため、
どの隣り合う 2 つのボールの色も異なり、条件をみたしています。
このとき、列に残ったボールの価値の和は V_1+V_2+V_4=1+5+4=10 です。
他にも 5 つのボールから 2 つのボールを取り除く方法であって、同じ色のボールが隣り合わないようにできるものは存在しますが、
3,5 番目のボールを取り除いた時に残ったボールの価値の和は最大となります。
よって、10 を出力します。
入力例 2
3 1 1 10 1 10 1 10
出力例 2
-1
どのようにボールを 1 つ取り除いても色 1 のボールが隣り合ってしまいます。
よって、 -1 を出力します。
入力例 3
3 1 1 1 2 2 3 3
出力例 3
5
必ずちょうど K 個のボールを取り除く必要があることに注意してください。
Score: 525 points
Problem Statement
There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.
Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.
Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.
Constraints
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
Output
If Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color, print the maximum possible total value of the remaining balls as an integer. Otherwise, print -1.
Sample Input 1
5 2 1 1 3 5 3 3 1 4 1 2
Sample Output 1
10
After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.
Hence, print 10.
Sample Input 2
3 1 1 10 1 10 1 10
Sample Output 2
-1
No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.
Sample Input 3
3 1 1 1 2 2 3 3
Sample Output 3
5
Note that exactly K balls must be removed.
実行時間制限: 2.5 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
店で N 個の商品が売られています。 i 個目の商品の価格は P_i 円、効用は U_i 、色は C_i です。
あなたは、これらの N 個の商品から何個か( 0 個でもよい)を選んで購入します。 このとき、購入した品物の合計価格は X 円以下でなければなりません。
あなたの満足度は、購入した商品の効用の合計を S、購入した商品の色の種類数を T としたとき、S+T \times K です。 ここで、K は入力で与えられる定数です。
あなたの満足度を最大化するように購入する商品を選んだとき、満足度を求めてください。
制約
- 1 \leq N \leq 500
- 1 \leq X \leq 50000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq X (1 \leq i \leq N)
- 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq N (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X K P_1 U_1 C_1 P_2 U_2 C_2 \vdots P_N U_N C_N
出力
答えを出力せよ。
入力例 1
3 10 5 1 3 1 7 4 2 4 5 1
出力例 1
17
1 個目、2 個目の商品を購入したとき、効用の合計 S は 7 で、色の種類数 T は 2 です。よって、満足度は 7+2 \times 5 = 17 です。また、満足度が 18 以上になるような購入の仕方は存在しないため、答えは 17 です。
入力例 2
5 30 3 5 4 3 11 20 1 9 10 4 7 5 2 16 15 4
出力例 2
44
2 個目、3 個目、4 個目の商品を購入したとき、効用の合計 S は 35 で、色の種類数 T は 3 です。よって、満足度は 35+3 \times 3 = 44 です。また、満足度が 45 以上になるような購入の仕方は存在しないため、答えは 44 です。
入力例 3
22 75 6426 9 309 9 5 470 5 17 481 12 27 352 14 1 191 18 7 353 20 9 99 15 20 401 17 46 434 19 11 459 22 10 317 19 15 440 18 17 438 19 25 461 22 5 320 22 1 476 21 11 315 3 8 112 9 11 438 13 19 362 8 10 422 13 10 152 21
出力例 3
67717
Score : 525 points
Problem Statement
There are N products for sale in a store. The i-th product has a price of P_i yen, a utility value of U_i, and a color C_i.
You will choose some subset of these N products to buy (possibly none). The total price of the chosen products must be at most X yen.
Your satisfaction is S + T \times K, where S is the sum of utilities of the chosen products, and T is the number of distinct colors among the chosen products. Here, K is a given constant.
You will choose products to maximize your satisfaction. Find the maximized satisfaction.
Constraints
- 1 \leq N \leq 500
- 1 \leq X \leq 50000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq X (1 \leq i \leq N)
- 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq N (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X K P_1 U_1 C_1 P_2 U_2 C_2 \vdots P_N U_N C_N
Output
Print the answer.
Sample Input 1
3 10 5 1 3 1 7 4 2 4 5 1
Sample Output 1
17
If you buy the 1st and 2nd products, the total utility S is 7, and the number of distinct colors T is 2. Thus, your satisfaction is 7 + 2 \times 5 = 17. No purchase plan makes your satisfaction 18 or greater, so the answer is 17.
Sample Input 2
5 30 3 5 4 3 11 20 1 9 10 4 7 5 2 16 15 4
Sample Output 2
44
If you buy the 2nd, 3rd, and 4th products, the total utility S is 35, and the number of distinct colors T is 3. Thus, your satisfaction is 35 + 3 \times 3 = 44. No purchase plan makes your satisfaction 45 or greater, so the answer is 44.
Sample Input 3
22 75 6426 9 309 9 5 470 5 17 481 12 27 352 14 1 191 18 7 353 20 9 99 15 20 401 17 46 434 19 11 459 22 10 317 19 15 440 18 17 438 19 25 461 22 5 320 22 1 476 21 11 315 3 8 112 9 11 438 13 19 362 8 10 422 13 10 152 21
Sample Output 3
67717