prithivMLmods/Coder-Stat

1 2 3<script type="text/x-mathjax-config">4  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});5</script>6<script language="JavaScript" type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML">7</script>8 9 10<H1> IOI 饅頭(IOI Manju)11</H1>12<br/>13 14<p>15Incredible Okashi Inc. は「途方もなくおいしいお菓子(incredible okashi)」を製作している会社である．ここでは略してIOI 社と呼ぶ．IOI 社は特製のIOI 饅頭を作ったので，それを販売することになった．IOI 社は$M$ 種類の饅頭を1 個ずつ作った．作られた$M$ 個の饅頭はすべて同じ大きさであるが，ひとつひとつ異なる味なので価格は様々であり，$i$ 番目$(1 \leq i \leq M)$ の饅頭の価格は$P_i$ 円である．16</p>17 18<p>19ところで，あなたはJust Odd Inventions 社を知っているだろうか？ この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである．ここでは略してJOI 社と呼ぶ．IOI 社は，饅頭を詰めるための高級な箱をJOI 社に発注することになった．JOI 社の製作する饅頭用の箱は$N$ 種類あり， $j$ 番目$(1 \leq j \leq N)$の箱は最大で$C_j$ 個の饅頭を詰められる大きさであり，販売価格は$E_j$ 円である．これらの$N$ 種類の箱のうちの何種類か(0 種類以上$N$ 種類以下) を1 個ずつ発注し，饅頭をそれらの箱に詰め分けてセットで販売することになった．各饅頭セットの価格は，それに含まれる饅頭の価格の合計である．20</p>21 22<p>23すべての饅頭セットが売れるとした場合，IOI 社が得ることができる利益の最大値はいくらだろうか．ここで利益とは，販売した饅頭セットの価格の合計から，発注した箱の価格の合計を引いた値である．なお，箱に詰めなかった饅頭については，IOI 社のスタッフがおいしくいただくため，利益には影響しないものとする．24</p>25 26 27 28<h2>課題</h2>29 30<p>31各饅頭の価格と，各箱の大きさと価格が与えられたとき，IOI 社が得ることができる利益の最大値を求めるプログラムを作成せよ．32</p>33 34 35<h2>入力</h2>36 37<p>38標準入力から以下のデータを読み込め．39</p>40 41<ul>42<li>1 行目には，整数 $M, N$ が空白を区切りとして書かれており，饅頭が $M$ 個，箱が $N$ 種類あることを表す．</li>43<li>続く $M$ 行のうちの $i$ 行目 $(1 \leq i \leq M)$ には，整数 $P_i$ が書かれており，$i$ 番目の饅頭の価格が $P_i$ 円であることを表す．</li>44<li>続く$N$ 行のうちの $j$ 行目 $(1 \leq j \leq N)$ には，整数 $C_j$, $E_j$ が空白を区切りとして書かれており， $j$ 番目の箱は最大で $C_j$ 個の饅頭を詰められる大きさであり，価格が $E_j$ 円であることを表す．</li>45</ul>46 47<h2>出力</h2>48 49<p>50標準出力に，IOI 社が得られる利益の最大値を円単位で表す整数を1 行で出力せよ．51</p>52 53 54<h2>制限</h2>55<p>56すべての入力データは以下の条件を満たす．57</p>58<ul>59<li>$1 \leq M \leq 10000$</li>60<li>$1 \leq N \leq 500$</li>61<li>$1 \leq P_i \leq 10000 (1 \leq i \leq M)$</li>62<li>$1 \leq C_j \leq 10000 (1 \leq j \leq N)$</li>63<li>$1 \leq E_j \leq 10000 (1 \leq j \leq N)$</li>64</ul>65 66 67<h2>入出力例</h2>68 69  <h3>入力例 1 </h3>  70 71  <pre>724 373180741607517076190772 100783 120794 25080</pre>81 82  <h3>出力例 1 </h3>  83 84  <pre>8548086</pre>87 88<p>89この例では，1 番目の箱(100 円) と2 番目の箱(120 円) を発注し，たとえば1 番目の箱に1 番目の饅頭と2 番目の饅頭を詰めて $180 + 160 = 340$ 円のセットとして販売，2 番目の箱に3 番目の饅頭と4 番目の饅頭を詰めて $170 + 190 = 360$ 円のセットとして販売すると，IOI 社の利益は $700 - 220 = 480$ 円となる．90</p>91 92<br>93 94  <h3>入力例 2 </h3>  95 96 97  <pre>982 299100010020001011 66661021 7777103</pre>104 105  <h3>出力例 2 </h3>  106 107  <pre>1080109</pre>110 111<p>112この例では，利益を最大化するためには箱を全く買わないのがよい．113</p>114<br>115 116  <h3>入力例 3 </h3>  117 118  <pre>11910 41202001212501223001233001243501254001265001273001282501292001303 14001312 5001322 6001331 900134</pre>135 136  <h3>出力例 3 </h3>  137 138  <pre>139450140</pre>141<br>142 143<div class="source">144<p class="source">145問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。146</p>147</div>148 149