레이팅 미적용あなたは,絵の展覧会を開催しようとしている.展覧会では,いくつかの絵を額縁に入れ,左から右に
一列に並べて展示する.
展覧会で展示する候補となる絵がN 枚あり,1 からN までの番号が付けられている.絵i (1 ≦i ≦N) の
大きさはS i,価値はVi である.
また,これらの絵を入れるための額縁がM 枚あり,1 からM までの番号が付けられている.額縁j
(1 ≦j ≦M) の大きさはC j である.額縁j には,大きさがC j 以下の絵のみを入れることができる.1 枚の
額縁には高々1 枚の絵しか入れることができない.
展示する絵はすべて何らかの額縁に入っていなければならない.見栄えを良くするため,展示する絵は
以下の条件を満たさなければならない:
• 左右に隣り合うどの2 枚の絵についても,右側の絵が入っている額縁の大きさは左側の絵が入ってい
る額縁の大きさ以上である.
• 左右に隣り合うどの2 枚の絵についても,右側の絵の価値は左側の絵の価値以上である.
あなたは,できるだけ多くの絵を展示したい.
展示候補の絵の枚数,額縁の枚数,及びそれらの大きさや価値が与えられたとき,展示する絵の枚数の
最大値を求めるプログラムを作成せよ.
• 1 ≦N ≦100 000.
• 1 ≦M ≦100 000.
• 1 ≦S i ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦Vi ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦C j ≦1 000 000 000 (1 ≦j ≦M).
- (10 点) N ≦10,M ≦10.
- (40 点) N ≦1000,M ≦1000.
- (50 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N M
S 1 V1
...
S N VN
C1
...
CM
標準出力に,展覧会に展示する絵の枚数の最大値を1 行で出力せよ.
第18 回日本情報オリンピック(JOI 2018/2019) 本選
2019 年2 月10 日(茨城県つくば市)
3 4
10 20
5 1
3 5
4
6
10
4
2
3 2
1 2
1 2
1 2
1
1
2
4 2
28 1
8 8
6 10
16 9
4
3
0
8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543
3