prithivMLmods/Coder-Stat

1<h1>展覧会(Exhibition)</h1>2 3<p>4  あなたは，絵の展覧会を開催しようとしている．展覧会では，いくつかの絵を額縁に入れ，左から右に一列に並べて展示する．5</p>6 7<p>8  展覧会で展示する候補となる絵が$N$ 枚あり，1 から$N$ までの番号が付けられている．絵$i$ ($1 \leq i \leq N$) の大きさは$S_i$，価値は$V_i$ である．9</p>10 11<p>12  また，これらの絵を入れるための額縁が$M$ 枚あり，1 から$M$ までの番号が付けられている．額縁$j$ ($1 \leq j \leq M$) の大きさは$C_j$ である．額縁$j$ には，大きさが$C_j$ 以下の絵のみを入れることができる．1 枚の額縁には高々1 枚の絵しか入れることができない．13</p>14 15<p>16  展示する絵はすべて何らかの額縁に入っていなければならない．見栄えを良くするため，展示する絵は以下の条件を満たさなければならない：17</p>18 19<ul>20<li>左右に隣り合うどの2 枚の絵についても，右側の絵が入っている額縁の大きさは左側の絵が入っている額縁の大きさ以上である．</li>21<li> 左右に隣り合うどの2 枚の絵についても，右側の絵の価値は左側の絵の価値以上である．</li>22</ul>23<p>24  あなたは，できるだけ多くの絵を展示したい．25</p>26 27<p>28  展示候補の絵の枚数，額縁の枚数，及びそれらの大きさや価値が与えられたとき，展示する絵の枚数の最大値を求めるプログラムを作成せよ．29</p>30 31<h2>入力</h2>32<p>33  入力は以下の形式で標準入力から与えられる．34</p>35<pre>36$N$ $M$37$S_1$ $V_1$38:39$S_N$ $V_N$40$C_1$41:42$C_M$43</pre>44 45<h2>出力</h2>46<p>47  標準出力に，展覧会に展示する絵の枚数の最大値を1 行で出力せよ．48</p>49 50<h2>制約</h2>51<ul>52<li>$ 1 \leq N \leq 100 000$.</li>53<li>$ 1 \leq M \leq 100 000$.</li>54<li>$ 1 \leq S i \leq 1 000 000 000 (1 \leq i \leq N)$.</li>55<li>$ 1 \leq V_i \leq 1 000 000 000 (1 \leq i \leq N)$.</li>56<li>$ 1 \leq C_j \leq 1 000 000 000 (1 \leq j \leq M)$.</li>57</ul>58  <!--59小課題601. (10 点) N ≦ 10，M ≦ 10．612. (40 点) N ≦ 1000，M ≦ 1000．623. (50 点) 追加の制約はない．63    -->64  65<h2>入出力例</h2>66  67<h3>入力例1 </h3>68<pre>693 47010 20715 1723 5734746751076477</pre>78<h3>出力例1</h3>79<pre>80281</pre>82 83<p>84  この入出力例では，左から順に(絵2, 額縁2)，(絵1, 額縁3) と並べることで，2 枚の絵を展示することができる．3 枚以上の絵を展示することはできないので，2 を出力する．ここで，(絵$i$, 額縁$j$) は，額縁$j$に入った絵$i$ を表す．85</p>86 87 88<h3>入力例2</h3>89<pre>903 2911 2921 2931 294195196</pre>97<h3> 出力例2</h3>98<pre>992100</pre>101 102<h3>入力例3</h3>103<pre>1044 210528 11068 81076 1010816 910941103111</pre>112<h3>出力例3</h3>113<pre>1140115</pre>116 117<h3>入力例4</h3>118<pre>1198 8120508917604 35617051121501958939 840246141122485338402 32896484123957730250 357542366124904165504 137209882125684085683 775621730126552953629 20004459127125090903 60730299012843325527812997975618313028423637131856448848132276518245133314201319134666094038135149542543136</pre>137 138<h3>出力例4</h3>139<pre>1403141</pre>142<br/>143<p>144  <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>145  <br/>146 147  <a href="https://www.ioi-jp.org/joi/2018/2019-ho/index.html">情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』</a>148</p>149