Submission #851989

#	Time	Username	Problem	Language	Result	Execution time	Memory
851989		Jere	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Item {
    int profit, weight, copies;

    // Default constructor
    Item() {
        profit = 0;
        weight = 0;
        copies = 0;
    }

    Item(int profit, int weight, int copies) {
        this->profit = profit;
        this->weight = weight;
        this->copies = copies;
    }
};

static bool cmp(struct Item a, struct Item b) {
    double r1 = (double)a.profit / (double)a.weight;
    double r2 = (double)b.profit / (double)b.weight;
    return r1 > r2;
}

int knap(int W, struct Item arr[], int N) {
    sort(arr, arr + N, cmp);
    int finalValue = 0;

    for (int i = 0; i < N && W > 0; i++) {
        while (arr[i].weight <= W && arr[i].copies > 0) {
            W -= arr[i].weight;
            finalValue += arr[i].profit;
            arr[i].copies--;
        }
    }

    return finalValue;
}

int main() {
    int w, n;
    cin >> w >> n;
    Item arr[n]; // Declare an array of Item structs

    for (int i = 0; i < n; i++) {
        cin >> arr[i].profit >> arr[i].weight >> arr[i].copies;
    }

    cout << knap(w, arr, n); // Call the knap function with the array
    return 0;
}

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