問題文

東西に細長い土地があります。 この土地は、N 個の区画が東西に並んだ形をしており、西から i 番目の区画は区画 i と呼ばれます。

それぞれの区画には地下資源があることがわかっており、区画 i の資源埋蔵量は A_i です。

1 以上 N 以下のそれぞれの整数 k について、次の問題の答えを求めてください。

• 連続する k 個の区画を選んだとき、それらの区画の資源埋蔵量の総和として考えられる最大値はいくらか。

制約

• 1 \leq N \leq 3000
• 1 \leq A_i \leq 10^9
• 入力される値はすべて整数である。

入力例 1

4
4 1 3 3

出力例 1

4
6
8
11

k=1 のとき、区画 1 を選ぶと資源埋蔵量の総和は 4 となり、これが最大です。

k=2 のとき、区画 3,4 を選ぶと資源埋蔵量の総和は 3+3=6 となり、これが最大です。

k=3 のとき、区画 1,2,3 を選ぶと資源埋蔵量の総和は 4+1+3=8 となり、これが最大です。

k=4 のとき、区画 1,2,3,4 を選ぶと資源埋蔵量の総和は 4+1+3+3=11 となり、これが最大です。

入力例 2

5
10 20 30 40 50

出力例 2

50
90
120
140
150

入力例 3

10
61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114

出力例 3

932678664
1438640644
2316123397
2792432058
3364262702
3720648516
4447740026
4804125840
4919183689
4980232903

問題文

長さ N の整数列 A、長さ M の整数列 B、整数 K が与えられます。 値 X,Y を以下のように定義します。

• X= \sum_{i=1}^N A_i \times K^{N-i} = A_1 \times K^{N-1} + A_2 \times K^{N-2} + ... + A_N \times K^0
• Y= \sum_{i=1}^M B_i \times K^{M-i} = B_1 \times K^{M-1} + B_2 \times K^{M-2} + ... + B_M \times K^0

X と Y のどちらが小さいかを求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 2 \leq K \leq 10^9
• 0 \leq A_i \leq K-1
• 1 \leq A_1
• 0 \leq B_i \leq K-1
• 1 \leq B_1
• 入力される値はすべて整数である。

入力例 1

3 3 10
1 2 3
1 2 4

出力例 1

X

X=123,Y=124 であり、 X<Y であるので X と出力します。

入力例 2

4 3 13
1 2 3 4
4 5 6

出力例 2

Y

入力例 3

4 4 2
1 1 0 1
1 1 0 1

出力例 3

Same

問題文

縦 H 行、横 W 列のマス目があります。 上から i 行目、左から j 列目のマスをマス (i,j) と呼ぶことにします。

それぞれのマスには、1 つの駒が置いてあります。 ショウさんは、このうち K 個の駒をマス目上から取り除きました。 i 番目の取り除いた駒は、マス (R_i,C_i) にあった駒です。

今からショウさんは、次の操作を 0 回以上行います。

• 駒を 1 つ選び、その駒が現在置かれているマスから、隣接する別のマスへと移動させる。 このとき、移動先のマスに別の駒があっても構わない。 なお、2 つのマスが隣接するとは、2 つのマスが辺を共有することを意味する。

ショウさんの目的は、マス目上のすべての駒が同じマスに置いてあるようにすることです。 ショウさんが目的を達成するために必要な最小の操作回数を求めてください。

制約

• 1 \leq H \leq 10^5
• 1 \leq W \leq 10^5
• 0 \leq K \leq \min(10^5,H \times W -1)
• 1\leq R_i \leq H
• 1\leq C_i \leq W
• (R_i,C_i) \neq (R_j,C_j) (i\neq j)
• 入力される値はすべて整数である。

入力例 1

2 3 3
1 2
2 1
2 2

出力例 1

3

操作を行う前の段階で駒が置かれているマスは、マス (1,1), (1,3), (2,3) の 3 つです。 次のように 3 回操作することで、すべての駒が同じマスに置かれます。

• マス (1,1) に置いてある駒をマス (1,2) へ移動させる。
• マス (1,2) に置いてある駒をマス (1,3) へ移動させる。
• マス (2,3) に置いてある駒をマス (1,3) へ移動させる。

2 回以下の操作で目的を達成することはできないので、3 が答えとなります。

入力例 2

5 5 10
2 2
2 5
1 3
2 4
2 3
1 5
2 1
1 4
1 2
1 1

出力例 2

28

入力例 3

100000 100000 0

出力例 3

500000000000000

入力例 4

2 2 3
1 2
2 1
2 2

出力例 4

0

問題文

N 本の竹があり、1 から N までの番号がつけられています。 時刻 0 において、すべての竹の高さは 0 です。 それぞれの竹は、時刻が 1 経過するごとに高さが 1 増えます。

ナオさんが竹を伐採するイベントが M 回予定されています。 i 番目のイベントは時刻 T_i に行われ、このイベントでは番号が L_i 以上 R_i 以下の竹をすべて伐採します。 ナオさんが高さ x の竹を伐採するとき、彼女は x 点を得ます。 また、伐採された竹は高さが 0 になりますが、その竹はこれ以降も伸び続けます。

M 回のイベントでナオさんが得る得点の総和を求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq T_1 < T_2 < \cdots < T_M \leq 10^9
• 1 \leq L_i \leq R_i \leq N
• 入力される値はすべて整数である。

入力例 1

4 2
2 1 2
5 2 3

出力例 1

12

1 番目のイベントが行われる時刻 2 では、竹の高さはそれぞれ 2,2,2,2 です。 竹 1 と 2 を伐採すると、竹の高さはそれぞれ 0,0,2,2 になります。

2 番目のイベントが行われる時刻 5 では、竹の高さはそれぞれ 3,3,5,5 です。 竹 2 と 3 を伐採すると、竹の高さはそれぞれ 3,0,0,5 になります。

2 回のイベントで伐採した竹の高さはそれぞれ 2,2,3,5 なので、その総和である 12 が答えです。

入力例 2

10 5
8 1 4
11 6 7
20 1 1
31 9 9
36 1 1

出力例 2

113

入力例 3

10 10
76724435 3 4
118633459 1 2
288866156 6 9
470883673 6 10
521545097 2 4
827053186 1 1
856004743 2 4
873331881 1 1
909855542 6 10
916091889 8 9

出力例 3

8003096514

問題文

1 から N までの番号のついた N 個のブロックがあります。 また、整数 K が与えられます。

魔法使いのコウさんは、魔法を唱えてこれらのブロックを消し去ろうとしています。 彼は、以下のような魔法を唱えることができます。

• 1 \leq l \leq r \leq N, r-l \geq K を満たす整数の組 (l,r) を選び、 番号が l 以上 r 以下の（まだ消されていない）ブロックをすべて消す。

つまり、彼が唱えられる魔法は (l,rの選び方の総数) =(N-K) \times (N-K+1) / 2 種類あります。

それぞれの魔法を唱えるか唱えないかの組み合わせは全部で 2^{(N-K) \times (N-K+1) / 2} 通りあります。 コウさんは、このうち最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかに興味を持っています。

コウさんのために、最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかを求めてください。 ただし、答えは非常に大きくなることがあるので、答えを 10^9+7 で割ったあまりを求めてください。

制約

• 1 \leq N \leq 5000
• 0 \leq K \leq N-1
• 入力される値はすべて整数である。

入力例 1

3 1

出力例 1

5

コウさんが唱えられる魔法は、(l,r)=(1,2),(2,3),(1,3) の 3 種類です。 最終的にブロックをすべて消し去ることのできる組み合わせは、以下の 5 通りです。

• (1,2) と (2,3)
• (1,2) と (1,3)
• (1,2) と (2,3) と (1,3)
• (2,3) と (1,3)
• (1,3)

入力例 2

10 5

出力例 2

30784

入力例 3

5000 250

出力例 3

844653816

問題文

2 次元平面上に、1 から N までの番号のついた N 個の国があります。 国 i は座標 (X_i,Y_i) にあります。

それぞれの国には航空会社があります。 国 i の航空会社は、X_j \leq X_i かつ Y_j \leq Y_i を満たすすべての j (j \neq i) について、 国 j との間に直通便を運航しています。 この直通便は双方向です。 つまり、国 i の航空会社の飛行機を利用して、国 i から国 j へ移動することも、 国 j から国 i へ移動することも可能です。 国 i の航空会社の飛行機は、1 度利用するたびに C_i 円の料金がかかります。

ケンさんは現在国 S にいて、国 T まで移動したいです。 飛行機を利用して移動するとき、飛行機の料金の合計の最小値を求めてください。

制約

• 2 \leq N \leq 10^5
• 0 \leq X_i \leq 10^9
• 0 \leq Y_i \leq 10^9
• 1 \leq C_i \leq 10^9
• (X_i,Y_i) \neq (X_j,Y_j) (i \neq j)
• 1 \leq S \leq N
• 1 \leq T \leq N
• S \neq T
• 飛行機のみを利用して国 S から国 T まで移動することができる。
• 入力される値はすべて整数である。

入力例 1

4 1 4
0 1 3
1 1 6
0 0 4
1 0 8

出力例 1

11

この例では、直通便は以下の 5 種類が存在します。

• 国 1 と国 3 を結ぶ直通便。国 1 の航空会社が運航しており、一度利用するのに 3 円かかる。
• 国 1 と国 2 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
• 国 2 と国 3 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
• 国 2 と国 4 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
• 国 3 と国 4 を結ぶ直通便。国 4 の航空会社が運航しており、一度利用するのに 8 円かかる。

国 1 から国 4 へ移動する場合は、国 1→3→4 と移動すると料金の合計が 11 円になり、これが最小です。

入力例 2

9 3 6
2 3 9
1 4 2
0 4 16
1 3 77
3 3 12
4 0 96
4 2 41
2 1 17
3 4 45

出力例 2

104

問題文

N 頂点の木があり、頂点には 1 から N までの番号が、辺には 1 から N-1 までの番号がついています。 辺 i は頂点 A_i と B_i を結ぶ辺です。

1 から M までの番号のついた M 人の人が、今からこの木の上を移動します。 人 i は、頂点 V_i から出発し、以下の操作をちょうど L_i 回行います。

• 今いる頂点に繋がっている辺を自由に一つ選び、その辺を通って隣の頂点へ移動する。 このとき、通った辺の番号が x なら、C_x 点を得る。

すべての i について、人 i が L_i 回の操作で得られる得点の総和の最大値を求めてください。

制約

• 2 \leq N \leq 10^5
• 1 \leq A_i < B_i \leq N
• 1 \leq C_i \leq 10^9
• 1 \leq M \leq 10^5
• 1 \leq V_i \leq N
• 1 \leq L_i \leq 10^9
• 入力で与えられるグラフは木である。
• 入力される値はすべて整数である。

入力例 1

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

出力例 1

10
5
19

人 1 は、次のように行動すると 3 回の操作で得られる得点の総和を最大化できます。

• 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
• 辺 3 を使って移動し、頂点 3 から頂点 4 に移動する。4 点を得る。
• 辺 3 を使って移動し、頂点 4 から頂点 3 に移動する。4 点を得る。

人 2 は、次のように行動すると 1 回の操作で得られる得点の総和を最大化できます。

• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

人 3 は、次のように行動すると 5 回の操作で得られる得点の総和を最大化できます。

• 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
• 辺 2 を使って移動し、頂点 3 から頂点 2 に移動する。2 点を得る。
• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
• 辺 1 を使って移動し、頂点 1 から頂点 2 に移動する。5 点を得る。
• 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

入力例 2

12
9 10 13
5 8 78
1 7 96
3 5 56
7 9 99
4 12 36
7 12 45
7 11 37
8 9 69
2 7 60
6 7 71
10
9 7
8 1
1 2
11 18
1 18
3 5
9 17
9 13
9 16
5 5

出力例 2

693
78
195
1720
1779
401
1683
1287
1584
444

問題文

今日から数えて i 日目のことを Day i と呼ぶことにします。 例えば、今日は Day 1、明日は Day 2 です。

マコさんは、1 から N までの番号がついた N 個の宿題を課されています。 彼女は、Day 1 から始めて 1 日あたり 1 個の宿題を選んで終わらせます。 宿題 i を Day A_i またはそれ以前に終わらせると、彼女は X_i 点を得ます。 また、Day (A_i+1) またはそれ以降に終わらせると、Y_i 点を得ます。 ここで、X_i > Y_i です。

マコさんは、それぞれの k (1 \leq k \leq N) について、Day k までに得られる得点の総和の最大値を知りたいです。 彼女の代わりにこれを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq Y_i < X_i \leq 10^9
• 入力される値はすべて整数である。

入力例 1

3
1 10 9
1 7 4
2 3 2

出力例 1

10
16
19

各 k における最適な宿題の終わらせ方は、以下のようになります。

k=1 の場合、Day 1 に宿題 1 を終わらせれば、10 点を得ます。

k=2 の場合、Day 1 に宿題 2 を、Day 2 に宿題 1 を終わらせれば、7+9=16 点を得ます。

k=3 の場合、Day 1 に宿題 2 を、Day 2 に宿題 3 を、Day 3 に宿題 1 を終わらせれば、7+3+9=19 点を得ます。

入力例 2

6
2 58 37
2 67 12
3 82 79
4 23 6
4 82 64
1 40 17

出力例 2

82
164
231
289
309
328

入力例 3

15
9 605824191 280849371
4 596581791 33288517
9 721865638 162970480
3 973186445 472655273
6 305716162 49621035
8 630727512 144854327
5 314582040 241964889
2 837187623 326231876
1 619623058 10421080
9 938725073 25997036
2 256037683 12811156
8 930775386 430074396
9 724058993 159628544
9 519111960 59073187
3 157350380 35127939

出力例 3

973186445
1911911518
2842686904
3679874527
4403933520
5125799158
5756526670
6376149728
6981973919
7253580890
7495545779
7554618966
7604240001
7639367940
7652179096