시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 106 | 67 | 61 | 75.309% |
Incredible Okashi Inc. は「途方もなくおいしいお菓子 (incredible okashi)」を製作している会社である.ここでは略して IOI 社と呼ぶ.IOI 社は特製の IOI 饅頭を作ったので,それを販売することになった.IOI 社は M 種類の饅頭を 1 個ずつ作った.作られた M 個の饅頭はすべて同じ大きさであるが,ひとつひとつ異なる味なので価格は様々であり,i 番目 (1 ≤ i ≤ M) の饅頭の価格は Pi 円である.
ところで,あなたは Just Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.IOI 社は,饅頭を詰めるための高級な箱を JOI 社に発注することになった.JOI 社の製作する饅頭用の箱は N 種類あり,j 番目 (1 ≤ j ≤ N)の箱は最大で Cj 個の饅頭を詰められる大きさであり,販売価格は Ej 円である.これらの N 種類の箱のうちの何種類か (0 種類以上 N 種類以下) を 1 個ずつ発注し,饅頭をそれらの箱に詰め分けてセットで販売することになった.各饅頭セットの価格は,それに含まれる饅頭の価格の合計である.
すべての饅頭セットが売れるとした場合,IOI 社が得ることができる利益の最大値はいくらだろうか.ここで利益とは,販売した饅頭セットの価格の合計から,発注した箱の価格の合計を引いた値である.なお,箱に詰めなかった饅頭については,IOI 社のスタッフがおいしくいただくため,利益には影響しないものとする.
各饅頭の価格と,各箱の大きさと価格が与えられたとき,IOI 社が得ることができる利益の最大値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
標準出力に,IOI 社が得られる利益の最大値を円単位で表す整数を 1 行で出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 25 | N ≤ 10. |
2 | 35 | Cj ≤ 10 (1 ≤ j ≤ N). |
3 | 40 | 追加の制限はない. |
4 3 180 160 170 190 2 100 3 120 4 250
480
この例では,1 番目の箱 (100 円) と 2 番目の箱 (120 円) を発注し,たとえば 1 番目の箱に 1 番目の饅頭と 2 番目の饅頭を詰めて 180 + 160 = 340 円のセットとして販売,2 番目の箱に 3 番目の饅頭と 4 番目の饅頭を詰めて 170 + 190 = 360 円のセットとして販売すると,IOI 社の利益は 700 − 220 = 480 円となる.
2 2 1000 2000 1 6666 1 7777
0
この例では,利益を最大化するためには箱を全く買わないのがよい.
10 4 200 250 300 300 350 400 500 300 250 200 3 1400 2 500 2 600 1 900
450