問題文

ギガ高校には A 個の教室があり，すべての教室は一辺が B メートルの正方形の形をしています．

この高校の教室の合計面積を求めてください．

制約

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• 入力はすべて整数

部分点

この問題には部分点は存在せず，すべてのテストケースに正解すると 100 点が与えられます．

入力例 1

4 3

出力例 1

36

教室の 1 個当たりの面積は 3×3=9 平方メートルです．

また，ギガ高校には教室が 4 個あるため，合計面積は 9×4=36 平方メートルとなります．

入力例 2

24 15

出力例 2

5400

教室の 1 個当たりの面積は 15×15=225 平方メートルです．

また，ギガ高校には教室が 24 個あるため，合計面積は 225×24=5400 平方メートルとなります．

入力例 3

100 100

出力例 3

1000000

問題文

GigaCode 社は毎年採用面接を行っています．
この会社では，採用において「技術力」「社会性」の 2 つの観点を重要視しています．採用に当たっては「技術力」「社会性」それぞれ 100 点満点で点数をつけ，それらに応じて以下の 2 つの条件を両方満たす人のみ合格とします．

• 技術力が X 点以上かつ社会性が Y 点以上である．
• 技術力と社会性の合計点が Z 点以上である．

さて，今年は N 人の大学生が応募しました．i 人目の応募者は，技術力の点数が A_i 点，社会性の点数が B_i 点でした．何人の応募者が採用面接に合格するか，求めてください．

制約

• 1 \leq N \leq 100
• 0 \leq A_i \leq 100
• 0 \leq B_i \leq 100
• 0 \leq X \leq 100
• 0 \leq Y \leq 100
• 0 \leq Z \leq 200
• 入力はすべて整数

出力

N 人のうち何人の応募者が採用面接に合格するか，整数で出力してください．

小課題 1 のヒント

小課題 1 では，すべてのテストケースが N = 1 です．つまり，以下の形式で入力が与えられます．

N X Y Z
A_1 B_1

そのとき，X \leq A_1, Y \leq B_1, Z \leq A_1 + B_1 のすべての条件を満たせば，1 人目の応募者が合格するので 1 と出力し，そうでない場合は 0 と出力するのが，小課題 1 の本質です．
なお，この小課題は，繰り返し処理等を使わなくても解くことができます．

小課題 2 のヒント

小課題 2 では，答えは必ず N になります．

小課題 3 のヒント

for 文などの繰り返し処理と，if 文などの条件分岐を使うと，解くことができます．

入力例 1

1 60 20 100
72 28

出力例 1

1

1 人目の応募者は，以下の条件を満たすため，合格となります．

• 技術力の点数が 72 点となり，合格基準である 60 点以上となる．
• 社会性の点数が 28 点となり，合格基準である 20 点以上となる．
• 技術力と社会性の合計点数が 72+28=100 点となり，合格基準である 100 点以上となる．

よって，合格人数は 1 人です．

なお，この入出力例は 1 つ目の小課題（小課題 1）の制約を満たします．また，2 つ目の小課題（小課題 2）の制約も満たします．

入力例 2

5 70 70 150
72 77
70 90
65 88
75 75
97 84

出力例 2

3

2 人目・4 人目・5 人目の応募者のみ合格となります．
この入出力例は N=1 ではないので，小課題 1 の制約を満たしません．

入力例 3

15 80 60 150
20 24
33 17
29 36
40 18
15 27
10 41
53 77
42 15
12 17
32 10
19 28
37 27
91 2
13 25
40 40

出力例 3

0

とても難しい採用試験です．

問題文

ギガ君は，「GigaCode 20XX」というイベントに参加するために，小遣いからパソコンを購入することになりました．今日を 1 日目とすると，彼は D 日目までにパソコンを購入しなければなりません．

1 日目の朝の段階で，彼が持っている小遣いの金額は 0 円です．また，i 日目の正午には小遣い a_i 円が彼に渡されます．

さて，パソコンの価格は毎日変動します．i 日目のパソコンの価格は b_i 円であり，この価格はその日の 0 時から 24 時まで変わりません．

D 日間分の小遣いの情報・パソコンの価格の情報が与えられたとき，彼が買うことのできるパソコンの価格としてあり得る最小値を求めてください．ただし，彼がパソコンを D 日目までに購入することができない場合は -1 と出力してください．なお，与えられた小遣い以外の金は使うことができないものとします．

制約

• 1 \leq D \leq 200 \ 000
• 1 \leq a_1, a_2, a_3, \dots, a_D \leq 200 \ 000
• 1 \leq b_1, b_2, b_3, \dots, b_D \leq 2 \ 000 \ 000 \ 000
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (20 点) D = 1 を満たす．
2. (40 点) D \leq 365 を満たす．
3. (40 点) 追加の制約はない．

入力例 1

1
120000
100000

出力例 1

100000

彼は 1 日目の夜の時点で 120 \ 000 円持っているため，1 日目の夜に 100 \ 000 円のパソコンを購入することができます．
よって，100000 と出力するのが正解です．

なお，この入出力例は，小課題 1 の制約，小課題 2 の制約を満たします．

入力例 2

1
70000
100000

出力例 2

-1

彼は 1 日目の夜の時点で 70 \ 000 円持っていますが，パソコンを購入するのに 100 \ 000 円かかるため，彼はパソコンを購入することができません．
よって，-1 と出力するのが正解となります．

入力例 3

5
10000 10000 10000 10000 10000
41210 27556 29018 42919 33762

出力例 3

29018

彼が 1 日目の夜にパソコンを購入しようとした場合：

• 所持金：10 \ 000 円
• パソコンの価格：41 \ 210 円 → 購入できない

彼が 3 日目の夜にパソコンを購入しようとした場合：

• 所持金：10 \ 000 + 10 \ 000 + 10 \ 000 = 30 \ 000 円
• パソコンの価格：29 \ 018 円 → 購入できる

彼が 5 日目の夜にパソコンを購入しようとした場合：

• 所持金：10 \ 000 + 10 \ 000 + 10 \ 000 + 10 \ 000 + 10 \ 000 = 50 \ 000 円
• パソコンの価格：33 \ 762 円 → 購入できる

また，彼は 2, 4 日目の夜にパソコンを購入することはできません．よって答えは 29 \ 018 円となります．

なお，この入出力例は，小課題 2 の制約を満たします．

入力例 4

5
10000 10000 10000 10000 10000
30000 29999 29998 29997 29996

出力例 4

29996

問題文

ギガ君は，パソコンを買い，プログラミングの勉強をし，会社に入り，金を儲け，そしてついに家を建設することとなりました！
彼の住むテラ市は H 行 W 列のマス目で表されます．上から i 行目，左から j 列目のマスは (i, j) で表されます．また，マス (i, j) の地価は A_{i, j} 円です．

さて，家は以下のように建設することができます．

• テラ市の中のいくつかのマス（土地）を選び，購入することができる．マス (i, j) を購入するのに A_{i, j} 円かかる．なお，購入するマスの領域は 1 つの長方形で表されなければならない．
• 購入した土地全体に家を建設する．S 個のマスを購入した場合，家を建設するのに S×K 円かかる．

例えば，K = 5 であるとき，(図1) のような建設を行う場合は (1+4)+(2 \times 5)=15 円，(図2) のような建設を行う場合は (6+3+4+1)+(4 \times 5)=34 円かかります．ただし図中の数は各マスの地価とします．

また，以下の (図3) や (図4) の灰色の部分の土地を購入することはできません．なぜなら，購入した土地の領域が 1 つの長方形で表されないからです．

彼は現在 V 円持っており，全財産を豪邸の購入に使うことができます．彼はできるだけ面積の大きい家を買いたいです．
現在彼が買うことのできる家として考えられる，最大の面積を求めてください．また，家を購入できない場合は 0 と出力してください．ただし，家の面積と購入した長方形領域の面積は同じものとします．

制約

• 1 \leq H, W \leq 125
• 1 \leq A_{i, j}, K \leq 1 \ 000 \ 000 \ 000
• 1 \leq V \leq 1 \ 000 \ 000 \ 000 \ 000 \ 000 (=10^{15})
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (11 点) H = 1, W = 1
2. (17 点) H = 1, W \leq 20
3. (28 点) H \leq 20, W \leq 20
4. (27 点) H \leq 75, W \leq 75
5. (17 点) 追加の制約はない．

入力例 1

1 1 200 500
300

出力例 1

1

彼は唯一のマスを購入し，家を建設すると，200 + 300 = 500 円かかり，ギリギリ足ります．
この入力例は，小課題 1 の制約を満たします．

入力例 2

1 8 10 200
30 40 10 20 30 40 10 20

出力例 2

6

例えば，彼が以下のように土地を購入したとしましょう．

その場合，土地を購入するのに 10 + 20 + 30 + 40 + 10 + 20 = 130 円，家を建設するのに 6 × 10 = 60 円かかるため，合計で 130 + 60 = 190 円必要ですが，200 円以下なので面積 6 の家が建設可能です．
なお，面積 7 以上の家を購入できるような方法はありません．
この入力例は，小課題 2 の制約を満たします．

入力例 3

5 5 10 17
12 19 25 13 25
14 16 18 11 10
19 17 24 26 12
23 11 16 19 14
18 23 27 11 16

出力例 3

0

この入力例では，家を購入することができません．そのため，0 と出力してください．

入力例 4

4 7 10 240
17 12 15 18 19 15 23
22 12 41 16 27 10 10
15 69 18 11 10 23 15
12 20 13 12 17 18 15

出力例 4

9

例えば，以下のように土地を買い，面積 9 の家を購入すると，235 円が必要となり，ギリギリ足ります．

問題文

ギガ通りは西から東へ一直線に走る，長さ L メートルの道路です．

E869120 君は最初ギガ通りの西端におり，分速 V_S メートルで残り D_S メートル走れる車に乗っています．

この通りにはこれ以外にも N 個の車があります．i 個目の車は西端から X_i メートルの位置にあり，分速 V_i メートルで残り D_i メートル走れます．

あなたは，車を 西から東の向きに 運転し，ギガ通りの東端にたどり着きたいです．

彼は，途中で車が停まっている場所まで運転してその車に乗り換えることもできます．乗り継ぎにかかる時間は 0 分として良いです．

さて，彼はギガ通りの東端にたどり着けるでしょうか？たどり着けない場合このことを報告し，たどり着ける場合は東端にたどり着くのに必要な最短時間 (分) を報告してください．

制約

• 0 \leq N \leq 2 \ 019
• 1 \leq L \leq 40 \ 075 \ 017
• 1 \leq X_1, X_2, \dots, X_N \leq L-1
• X_1, X_2, \dots, X_N はすべて異なる
• 1 \leq V_S, V_1, V_2, \dots, V_N \leq 100 \ 000
• 1 \leq D_S, D_1, D_2, \dots, D_N \leq L
• 入力はすべて整数

出力

ギガ通りの東端に何をやってもたどり着けないならば impossible と出力してください．
たどり着ける場合は，その際にかかる最短時間 (分) を出力してください．これは小数点以下何桁でも出力して良いですが，答えとの誤差（絶対誤差または相対誤差）が 10^{-5} 以内であったときのみ正解とみなされます．

入力例 1

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

出力例 1

4.000000000000000000000

次のような移動をすると 4 分でギガ通りの東端にたどり着くことができ、これが最短です。

• まず、最初に乗る車で西端から 3 メートルのところまで進む。これに 3/1 = 3 分かかる。
• 次に、1 個目の車で西端から 6 メートルのところまで進む。これに 3/5 = 0.6 分かかる。
• 最後に、2 個目の車で東端 (西端から 10 メートルのところ) まで進む。これに 4/10 = 0.4 分かかる。
• 合計 3 + 0.6 + 0.4 = 4 分で、東端にたどり着くことができた。

入力例 2

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

出力例 2

4.400000000000000355271

次のような移動をすると 4.4 分でギガ通りの東端にたどり着くことができ、これが最短です。

• まず、最初に乗る車で西端から 3 メートルのところまで進む。これに 3/1 = 3 分かかる。
• そして、1 個目の車で東端 (西端から 10 メートルのところ) まで進む。これに 7/5 = 1.4 分かかる。
• 合計 3 + 1.4 = 4.4 分で、東端にたどり着くことができた。

入力例 3

2 10
1 4
3 1 2
6 1 10

出力例 3

impossible

この場合、どうやってもギガ通りの東端にたどり着くことはできません。
また、入出力例 3 は小課題 4「V_S = 1、V_i = 1」の制約を満たします。

入力例 4

0 1
99991 1

出力例 4

0.000010000900081007291

答えは 1.00009e-05 のような形式ではなく、0.00001000090008 のような形式で出力する必要があることに注意してください。
また、入出力例 4 は小課題 1「N = 0」の制約を満たします。

入力例 5

1 100
5 60
50 7 90

出力例 5

17.142857142857142349612

この場合、西端から 50 メートルのところで乗り継ぐのが最適となります。
また、入出力例 5 は小課題 2「N = 0 または N = 1」の制約を満たします。

入力例 6

4 1000
37 426
725 16 612
237 19 458
516 13 509
408 17 400

出力例 6

46.861585850556437549130

絶対誤差または相対誤差が 10^{-5} 以内ならば正解とみなされますので、46.861585 や 46.86159 などと出力しても正解となります。

問題文

ギガコード君は家を買いました．この家は，左右に H 分割，前後に W 分割された合計 H \times W 個の区画に分かれています．そのうち左から i 番目，前から j 番目のマスを (i, j) で表します．

そのうち N 個の区画には物が置かれています．i 個目の物は，区画 (r_i, c_i) 全体を占めています．また，これらの物が動くことはありません．

ギガコード君は，この家にクローゼットを 1 つ設置することにしました．クローゼットは家の外壁に平行な長方形でなければならず，クローゼットのある区画に物が置かれていてはなりません．しかし，地震が起きた時にクローゼットが動くと良くないので，次の条件を満たす置き方のうち 1 つを選ぶことにしました．

• クローゼットを向きを変えずにどんな方向に動かそうとしても，物や家の外壁に当たって動かせない．

例えば，次のようなクローゼットの配置ができます．

しかし，条件を満たさないクローゼットの配置はできません．

条件を満たすようなクローゼットの配置はいくつあるか求めてください．

制約

• 1 \leq H \leq 5 \ 000
• 1 \leq W \leq 5 \ 000
• 0 \leq N \leq 201 \ 900
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• N 個の物はすべて異なる区画に置かれている
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (2 点) H = 1, W = 1
2. (11 点) H = 1, W \leq 25
3. (11 点) H \leq 25, W \leq 25
4. (19 点) N \leq 10
5. (16 点) H \leq 100, W \leq 100
6. (17 点) H \leq 350, W \leq 350
7. (19 点) H \leq 1500, W \leq 1500
8. (5 点) 追加の制約はない．

注意

入力のサイズが大きいので、高速な入出力（C++ の場合 scanf/printf など）を使うことが推奨されています．