제출 #578076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578076		DL1234	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	300 KiB

knapsack

#include <iostream>
#include <queue>

using namespace std;

struct item{
    int p, w, n;
    float r;
    bool operator<(const item& o) const
    {
        return r <= o.r;
    }
};

int main() {
    int s, n;
    cin >> s >> n;
    priority_queue<item> items;
    for (int i=0;i<n;i++){
        item j;
        cin >> j.p >> j.w >> j.n;
        j.r = (float)j.p/(float)j.w;
        items.push(j);
    }

    int totalProfit = 0;
    int remainingWeight = s;
    while (items.size() != 0){
        item i = items.top();
        items.pop();

        if (i.w > remainingWeight) continue;
        int maxNum = ((int)remainingWeight/(int)i.w) > i.n ? i.n : ((int)remainingWeight/(int)i.w);
        totalProfit += maxNum * i.p;
        remainingWeight = remainingWeight-(i.w*maxNum);
    }
    cout << totalProfit << endl;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27