問題文

音楽が好きな初夏は，ピアノの演奏能力を競うコンクールに出場した．

コンクールでは，初夏の演奏に対して N 人の審査員が採点した．i 人目の審査員 (1 \leqq i \leqq N) は A_i 点を付けた．ただし，A_1, A_2, \dots, A_N はすべて相異なる．このコンクールにおける初夏の総合得点は，審査員のうち最高点と最低点を付けた人を除く N-2 人の審査員の点数の合計である．

N 人の審査員が付けた点数が与えられたとき，初夏の総合得点を求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 50．
• 0 \leqq A_i \leqq 100 (1 \leqq i \leqq N)．
• A_i \neq A_j (1 \leqq i \lt j \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (50 点) N = 3．
2. (50 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

3
50 90 80

出力例 1

80

3 人の審査員がそれぞれ 50, 90, 80 点を付けた．最高点 90 点と最低点 50 点を除外した 80 点が，初夏の総合得点となる．

この入力例はすべての小課題の制約を満たす．

入力例 2

3
72 100 64

出力例 2

72

3 人の審査員がそれぞれ 72, 100, 64 点を付けた．最高点 100 点と最低点 64 点を除外した 72 点が，初夏の総合得点となる．

この入力例はすべての小課題の制約を満たす．

入力例 3

5
99 96 100 98 97

出力例 3

294

最高点 100 点と最低点 96 点を除外すると，残る 3 人の審査員の点数は 99, 98, 97 点となる．したがって，初夏の総合得点は 99 + 98 + 97 = 294 点となる．

この入力例は小課題 2 の制約を満たす．

入力例 4

8
0 80 40 75 90 70 85 100

出力例 4

440

最高点 100 点と最低点 0 点を除外すると，残る 6 人の審査員の点数は 80, 40, 75, 90, 70, 85 点となる．したがって，初夏の総合得点は 80 + 40 + 75 + 90 + 70 + 85 = 440 点となる．

この入力例は小課題 2 の制約を満たす．

問題文

JOI 高校の生徒である葵は，図書室で巻物を見つけた．この巻物には N 個の整数が一列に書かれており，左から i 番目 (1 \leqq i \leqq N) の数は A_i である．

葵は巻物を見て，「この N 個の整数の中から 3 個を選んで，左から順に x, y, z としたとき，x \times y = z となるような整数の選び方は何通りあるのか」という疑問を持った．

巻物に書かれた N 個の整数が与えられたとき，葵の疑問の答えを求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 100．
• 1 \leqq A_i \leqq 999 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (20 点) N = 3．
2. (80 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

3
21 13 273

出力例 1

1

A_1, A_2, A_3 を選ぶと，21 \times 13 = 273 となる．したがって，葵の疑問の答えは 1 通りである．

この入力例はすべての小課題の制約を満たす．

入力例 2

3
10 5 2

出力例 2

0

A_1, A_2, A_3 を選んでも，「10 \times 5 = 2」とはならない．したがって，葵の疑問の答えは 0 通りである．

この入力例はすべての小課題の制約を満たす．

入力例 3

5
4 2 2 8 16

出力例 3

4

3 個の整数を選んで，左から順に x, y, z としたとき，x \times y = z となるような整数の選び方は，以下の 4 通りがある．

• A_1, A_2, A_4 を選ぶと，4 \times 2 = 8 となる．
• A_1, A_3, A_4 を選ぶと，4 \times 2 = 8 となる．
• A_2, A_4, A_5 を選ぶと，2 \times 8 = 16 となる．
• A_3, A_4, A_5 を選ぶと，2 \times 8 = 16 となる．

この入力例は小課題 2 の制約を満たす．

入力例 4

10
1 1 1 1 1 1 1 1 1 1

出力例 4

120

この入力例は小課題 2 の制約を満たす．

問題文

JOI 高校において，ある議題に関して「賛成」か「反対」かを問う採決が行われ，N 人の生徒が順番に投票を行った．生徒は自分の投票前に，それまでに投票した他の生徒がどちらに投票したかを知ることができた．

i 番目 (1 \leqq i \leqq N) に投票した生徒は，次の条件を満たしたとき「賛成」に投票し，満たさなかったとき「反対」に投票した．

• 直前に投票した X_i 人の生徒，すなわち i-1,i-2,...,i-X_i 番目に投票した生徒のうち，Y_i 人以上が「賛成」に投票した．

ただし， Y_i=0 のときは他の生徒の投票に関わらず「賛成」に投票し，Y_i=X_i+1 のときは他の生徒の投票に関わらず「反対」に投票したとする．

各生徒の投票についての情報が与えられたとき，「賛成」に投票した生徒の人数を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 500\,000．
• 0 \leqq X_i \leqq i-1 (1 \leqq i \leqq N)．
• 0 \leqq Y_i \leqq X_i+1 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (28 点) N \leqq 3\,000．
2. (32 点) X_i = i-1 (1 \leqq i \leqq N)．
3. (40 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

4
0 1
1 0
1 1
3 3

出力例 1

2

投票は，以下のように 4 人の生徒によって順番に行われた．

1. 1 番目に投票した生徒は，Y_1=X_1+1 であるため，「反対」に投票した．
2. 2 番目に投票した生徒は，Y_2=0 であるため，「賛成」に投票した．
3. 直前に投票した X_3(=1) 人の生徒のうち「賛成」に投票したのは 1 人で，これは Y_3(=1) 人以上である．そのため，3 番目に投票した生徒は「賛成」に投票した．
4. 直前に投票した X_4(=3) 人の生徒のうち「賛成」に投票したのは 2 人で，これは Y_4(=3) 人以上ではない．そのため，4 番目に投票した生徒は「反対」に投票した．

「賛成」に投票した生徒は 2 人である．したがって，2 を出力する．

この入力例は小課題 1,3 の制約を満たす．

入力例 2

5
0 0
1 1
2 3
3 1
4 3

出力例 2

4

この入力例はすべての小課題の制約を満たす．

入力例 3

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

出力例 3

4

この入力例は小課題 1,3 の制約を満たす．

問題文

果物好きのビ太郎は，いちごのつかみ取りに挑戦することにした．ビ太郎の目の前には 1 脚の机がある．机は長方形の形をしており，縦 H 行，横 W 列のマス目状に区切られている．机には N 個のいちごが置かれており，i 番目 (1 \leqq i \leqq N) のいちごは上から A_i 行目，左から B_i 列目のマスにある．複数のいちごが同じマスに置かれている可能性もある．

ビ太郎は机から，縦 3 行，横 3 列の正方形の領域をなす 9 個のマスを選び，それらのマスにあるいちごをすべて取る．この動作は 1 回だけ行う．

ビ太郎は，なるべく多くのいちごを取りたい．

机の大きさといちごの位置についての情報が与えられたとき，取れるいちごの個数の最大値を求めるプログラムを作成せよ．

制約

• 3 \leqq H \leqq 1\,000\,000\,000．
• 3 \leqq W \leqq 1\,000\,000\,000．
• 1 \leqq N \leqq 60\,000．
• 1 \leqq A_i \leqq H (1 \leqq i \leqq N)．
• 1 \leqq B_i \leqq W (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (14 点) H \leqq 1\,000，W \leqq 1\,000，N \leqq 20．
2. (16 点) H \leqq 1\,000，W \leqq 1\,000．
3. (29 点) H \leqq 1\,000\,000，N \leqq 500．
4. (15 点) H = 3．
5. (20 点) H \leqq 1\,000\,000．
6. (6 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

4 5
7
1 1
1 5
2 2
2 4
3 3
4 2
4 4

出力例 1

5

いちごの配置は図のようになっている (赤い丸がいちごを表す)．

太枠で囲った領域をなすマスを選ぶことで，5 個のいちごが取れる．

5 個よりも多くのいちごを取ることはできないので，5 を出力する．

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす．

入力例 2

3 5
6
1 1
1 2
2 1
2 4
2 4
3 4

出力例 2

4

複数のいちごが同じマスに置かれていることもある．

この入力例はすべての小課題の制約を満たす．

入力例 3

3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

出力例 3

9

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 4

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

出力例 4

4

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす．

問題文

JOI 美術館には，N 枚の絵が横一列に飾られている．美術館に展示されている絵には M 個の種類があり，1 から M までの番号が付けられている．左から i 番目 (1 \leqq i \leqq N) の絵の種類は A_i であり，価値は V_i である．ここで，V_i は負の数になることもある．

来月，JOI 美術館では「エゴイ展 2022」が開催予定であり，多くの来客が見込まれるため，見栄えを良くしたい．そこで館長の理恵さんは，隣り合う絵が同じ種類にならないように，いくつかの絵を撤去することにした．

一方で，評判を高めるため，残された絵の価値の合計をできるだけ大きくしたい．

絵の枚数，絵の種類数，N 枚の絵の情報が与えられたとき，残された絵の価値の合計として考えられる最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 150\,000．
• 1 \leqq M \leqq N．
• 1 \leqq A_i \leqq M (1 \leqq i \leqq N)．
• -10\,000 \leqq V_i \leqq 10\,000 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (4 点) M = 1，N \leqq 15，V_i \geqq 1 (1 \leqq i \leqq N)．
2. (17 点) V_i \geqq 1 (1 \leqq i \leqq N)．
3. (21 点) N \leqq 15．
4. (27 点) N \leqq 100．
5. (19 点) M \leqq 100．
6. (12 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

3
1
1 107
1 123
1 100

出力例 1

123

左から 2 番目の絵のみを残した場合，価値の合計は V_2 = 123 となる．

この入力例はすべての小課題の制約を満たす．

入力例 2

4
3
1 204
2 168
2 277
1 219

出力例 2

700

左から 1, 3, 4 番目の絵を残すのが最適である．

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．

入力例 3

3
2
1 5
2 -1
1 5

出力例 3

9

すべての絵を残すのが最適である．

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 4

6
4
1 -123
2 -123
3 -123
4 -123
4 -123
3 -123

出力例 4

0

絵を 1 枚も残さないのが最適である．

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 5

30
4
2 -1358
4 -1405
4 2003
3 -1148
2 -1527
2 -2015
4 -2910
1 2133
2 2185
1 2249
3 1058
1 -1907
2 -3190
1 -2701
3 -2640
1 1685
3 1855
4 2398
3 -3158
2 1947
3 2947
2 -2197
4 1398
2 -3011
4 -1971
1 -2829
1 3094
2 2704
4 -2592
3 2910

出力例 5

30566

この入力例は小課題 4, 5, 6 の制約を満たす．

問題文

IOI 国には，1 から N までの番号が付けられた N 個の町と，1 から M までの番号が付けられた M 本の道がある．

それぞれの道は，タクシーでのみ通行可能である．道 i (1 \leqq i \leqq M) のタクシーは町 A_i と町 B_i を双方向に移動でき，そのタクシーの色は，C_i = 1 のとき赤色，C_i = 2 のとき青色である．タクシーには料金がかかり，乗車すると以下のように所持金が変化する．

• 乗車前の所持金を a 円とする．
• タクシーが赤色の場合，乗車後の所持金が a - 1 円になる．
• タクシーが青色の場合，乗車後の所持金が「a \div 2 を整数に切り捨てた値」円になる．

あなたは IOI 国の町 1 に住んでおり，以下の Q 個の質問の答えを知っておきたい．j 番目 (1 \leqq j \leqq Q) の質問は以下の通りである．

• 町 1 から出発し，1 円以上の所持金を残した状態で町 T_j に到着するために，最初に少なくとも何円の所持金を持っている必要があるか．ただし，答えが L 円よりも大きい場合は，代わりに Large と答えよ．

町とタクシーの情報，そして質問の内容が与えられたとき，すべての質問に答えるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• N - 1 \leqq M \leqq 200\,000．
• 1 \leqq Q \leqq 200\,000．
• 1 \leqq L \leqq 1\,000\,000\,000．
• 1 \leqq A_i \lt B_i \leqq N (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i \lt j \leqq M)．
• 1 \leqq C_i \leqq 2 (1 \leqq i \leqq M)．
• 2 \leqq T_j \leqq N (1 \leqq j \leqq Q)．
• どの町の間も，いくつかの道を通って行き来できる．
• 入力される値はすべて整数である．

小課題

1. (9 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M)，Q = 1，N \leqq 100，L \leqq 100．
2. (19 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M)，Q = 1．
3. (19 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M)．
4. (16 点) N \leqq 50\,000，M \leqq 50\,000，Q = 1，C_i = 1 (1 \leqq i \leqq M)．
5. (20 点) N \leqq 50\,000，M \leqq 50\,000，Q = 1．
6. (12 点) N \leqq 50\,000，M \leqq 50\,000，Q \leqq 50\,000．
7. (5 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

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

出力例 1

10

町 1 → 町 2 → 町 3 → 町 4 → 町 5 の経路で移動するならば，順に青，赤，青，赤のタクシーに乗ることになる．すると，最初に所持金が 10 円あった場合，所持金は 10 円 → 5 円 → 4 円 → 2 円 → 1 円となり，1 円以上を残した状態で町 5 に到着できる．

一方，最初の所持金が 9 円以下の場合，1 円以上を残した状態で町 5 に到着することはできない．

この入力例は小課題 1, 2, 3, 5, 6, 7 の制約を満たす．

入力例 2

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

出力例 2

Large
22
4

例えば，1 番目の質問について考えよう．

町 1 から出発して町 10 に移動するとき，町 1 → 町 2 → … → 町 9 → 町 10 の経路をたどることになる．しかし，最初に L (= 25) 円持っていたとしても，タクシーを使うごとに所持金が 25 円 → 12 円 → 11 円 → 10 円 → … と減っていき，1 円以上を残して町 10 にたどり着くことはできない．よって，Large と出力しなければならない．

この入力例は小課題 3, 6, 7 の制約を満たす．

入力例 3

5 6 1 1000000000
1 4 1
1 5 1
4 5 1
3 4 1
3 5 1
2 3 1
2

出力例 3

4

町 1 → 町 5 → 町 3 → 町 2 の経路で移動するならば，赤いタクシーに 3 回乗ることになる．すると，最初に所持金が 4 円あった場合，所持金は 4 円 → 3 円 → 2 円 → 1 円となり，1 円以上を残した状態で町 2 に到着できる．

一方，最初の所持金が 3 円以下の場合，1 円以上を残した状態で町 2 に到着することはできない．

この入力例は小課題 4, 5, 6, 7 の制約を満たす．

入力例 4

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

出力例 4

2
Large
7
5
3

この入力例は小課題 6, 7 の制約を満たす．