prithivMLmods/Coder-Stat

1 2 3 4<H1>古本屋(Books)  </H1>5 6 7<p>8あなたの町にはJOI 古本店という老舗の古本屋があり，あなたはJOI 古本店をよく利用している．それぞれの本には基準価格が定まっており，JOI 古本店に行けばその価格で買い取ってもらえる．9</p>10 11<p>12JOI 古本店では，本を小説,漫画,雑誌など10 種類のジャンルに分類して扱っている．ジャンルには1から10 までの番号が付けられている．JOI 古本店には，同じジャンルの本をまとめて買い取ってもらうと高値で買い取ってくれるというサービスがある．具体的には，同じジャンルの本をまとめてT 冊買い取ってもらう場合，そのジャンルの本の一冊あたりの買取価格が基準価格よりT - 1 円高くなる．例えば，同じジャンルで基準価格100 円，120 円，150 円の本をまとめてJOI 古本店に売ったとすると，買取価格はそれぞれ102 円，122 円，152 円となる．13</p>14 15<p>16さて，あなたは一身上の都合で急遽引越しをすることになった．あなたはN 冊の本を持っているが，新しい住居にすべての本を持っていくことは困難なため，<i>N</i> 冊の本のうち<i>K</i> 冊をJOI 古本店に売ることにした．17</p>18 19 20<h2>課題</h2>21<p>22<i>N</i> 冊の本それぞれの基準価格とジャンルの番号が与えられるとき，合計買取価格の最大値を求めるプログラムを作成せよ．23</p>24 25<h2>制限</h2>26<p>272 &le; <i>N</i> &le; 2000 &nbsp;&nbsp;&nbsp;あなたが持っている本の冊数<br>281 &le; <i>K</i> &lt; <i>N</i> &nbsp;&nbsp;&nbsp;JOI 古本店に売る本の冊数<br>291 &le; <i>C<sub>i</sub></i> &le; 100000 = 10<sup>5</sup> &nbsp;&nbsp;&nbsp;<i>i</i> 番目の本の基準価格<br>301 &le; <i>G<sub>i</sub></i> &le; 10 &nbsp;&nbsp;&nbsp;<i>i</i> 番目の本のジャンルの番号31</ul>32 33<h2>入力</h2>34 35<p>36標準入力から以下の入力を読み込め．37</p>38 39<ul>40<li> 1 行目には整数<i>N</i>, <i>K</i> が空白を区切りとして書かれており，あなたの持っている本の冊数が<i>N</i> で，そのうち<i>K</i> 冊をJOI 古本店に売ることを表す．41</li>42<li> 続く<i>N</i> 行にはあなたの持っている本の情報が書かれている．<i>i</i> + 1 行目(1 &le; <i>i</i> &le; <i>N</i>) には，整数<i>C<sub>i</sub></i>,<i>G<sub>i</sub></i>が空白を区切りとして書かれており，<i>i</i> 番目の本の基準価格が<i>C<sub>i</sub></i> で，ジャンルの番号が<i>G<sub>i</sub></i> であることを表す．</li>43</ul>44 45 46<h2>出力</h2>47<p>48標準出力に，合計買取価格の最大値を表す整数を1 行で出力せよ．49</p>50 51<h2>採点基準</h2>52<p>53採点用データのうち，<br>54配点の20% 分については，<i>N</i> &le; 20 を満たす．<br>55配点の20% 分については，すべての本のジャンルは1 または2 である．<br>56配点の10% 分については，これら2 つの条件の両方を満たす．<br>57配点の30% 分については，これら2 つの条件の少なくとも一方を満たす．<br>58</p>59 60 61<h2>入出力の例</h2>62 63<h3>入力例</h3>  64 65<pre>667 46714 16813 26912 37014 2718 27216 37311 274</pre>75 76<h3>出力例</h3>  77 78<pre>796080</pre>81 82<p>83この入力例では，2 番目，4 番目，6 番目，7 番目の4 冊の本を売ったとき，ジャンル2 の本の買取価格が1 冊あたり2 円高くなるので，これらの本の買取価格は以下のようになる．84</p>85 86<table style="margin-left: 50px; margin-right: 50px;">87 <tr>88  <th width="100" align="left">番号</th>  89  <th width="100" align="left">基準価格</th>  90  <th width="100" align="left">ジャンル</th>  91  <th width="100" align="left">買取価格</th>  92 </tr>93 <tr>94<td>95  <pre>962974986997100</pre>101 </td>102 <td>103<pre>10413105141061610711108</pre>109  </td>110<td>111  <pre>1122113211431152116</pre>117 </td>118 <td>119<pre>12015121161221612313124</pre>125  </td>126 </tr>127</table>128 129 130<p>131よって合計買取価格は15 + 16 + 16 + 13 = 60 円である．このとき合計買取価格は最大となる．132</p>133 134<div class="source">135<p class="source">136問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。137</p>138</div>139 140 141 142