oj.uz

Submission #578076

# Submission time Handle Problem Language Result Execution time Memory
578076 2022-06-16T02:23:05 Z DL1234 Knapsack (NOI18_knapsack) C++17
12 / 100
 1 ms 300 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -