展覧会 (Exhibition)
日本語
Language
Contribute a translation- Time limit
- 1000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
あなたは，絵の展覧会を開催しようとしている．展覧会では，いくつかの絵を額縁に入れ，左から右に一列に並べて展示する．
展覧会で展示する候補となる絵が \(N\) 枚あり，\(1\) から \(N\) までの番号が付けられている．絵 \(i\) (\(1 \leqq i \leqq N\)) の大きさは \(S_i\)，価値は \(V_i\) である．
また，これらの絵を入れるための額縁が \(M\) 枚あり，\(1\) から \(M\) までの番号が付けられている．額縁 \(j\) (\(1 \leqq j \leqq M\)) の大きさは \(C_j\) である．額縁 \(j\) には，大きさが \(C_j\) 以下の絵のみを入れることができる．\(1\) 枚の額縁には高々 \(1\) 枚の絵しか入れることができない．
展示する絵はすべて何らかの額縁に入っていなければならない．見栄えを良くするため，展示する絵は以下の条件を満たさなければならない：
- 左右に隣り合うどの \(2\) 枚の絵についても，右側の絵が入っている額縁の大きさは左側の絵が入っている額縁の大きさ以上である．
- 左右に隣り合うどの \(2\) 枚の絵についても，右側の絵の価値は左側の絵の価値以上である．
あなたは，できるだけ多くの絵を展示したい．
展示候補の絵の枚数，額縁の枚数，及びそれらの大きさや価値が与えられたとき，展示する絵の枚数の最大値を求めるプログラムを作成せよ．
Input
入力は以下の形式で標準入力から与えられる．
\(N\) \(M\)
\(S_1\) \(V_1\)
\(\vdots\)
\(S_N\) \(V_N\)
\(C_1\)
\(\vdots\)
\(C_M\)
Output
標準出力に，展覧会に展示する絵の枚数の最大値を \(1\) 行で出力せよ．
Constraints
- \(1 \leqq N \leqq 100\,000\)．
- \(1 \leqq M \leqq 100\,000\)．
- \(1 \leqq S_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．
- \(1 \leqq V_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．
- \(1 \leqq C_j \leqq 1\,000\,000\,000\) (\(1 \leqq j \leqq M\))．
Subtasks
- (\(10\) 点) \(N \leqq 10\)，\(M \leqq 10\)．
- (\(40\) 点) \(N \leqq 1\,000\)，\(M \leqq 1\,000\)．
- (\(50\) 点) 追加の制約はない．
Examples
3 4 10 20 5 1 3 5 4 6 10 4
2
この入出力例では，左から順に (絵 \(2\), 額縁 \(2\))，(絵 \(1\), 額縁 \(3\)) と並べることで，\(2\) 枚の絵を展示することができる．\(3\) 枚以上の絵を展示することはできないので，\(2\) を出力する．ここで，(絵 \(i\), 額縁 \(j\)) は，額縁 \(j\) に入った絵 \(i\) を表す．
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
Notes
JOI 2019 · JCIOI · CC BY-SA 4.0
Tags
No tags yet