oj.uz

Submission #892097

# Submission time Handle Problem Language Result Execution time Memory
892097 2023-12-24T22:05:08 Z cogentcoder73 Knapsack (NOI18_knapsack) C++17
12 / 100
 0 ms 440 KB 
#include <bits/stdc++.h>
using namespace std;

struct Item {
    int V, W, K;
    Item() {
        V = 0;
        W = 0;
        K = 0;
    }
    Item(int v, int w, int k) {
        V = v;
        W = w;
        K = k;
    }
    bool operator< (Item other) {
        if (W != other.W) return W < other.W;
        return V < other.V;
    }
};

int main() {
    int S, N;
    cin >> S >> N;

    Item items[N];
    for (int i = 0; i < N; i++) {
        cin >> items[i].V >> items[i].W >> items[i].K;
        items[i].K = min(items[i].K, S/items[i].W);
    }

    sort(items, items + N);

    vector<pair<int, int>> itemList[S + 1];
    int ind = 0;
    int curW, delW;
    for (int w = 1; w <= S; w++) {
        itemList[w].clear();
        curW = 0;
        while (ind < N && items[ind].W == w && curW < S) {
            delW = min(items[ind].K, S - curW);
            itemList[w].push_back({delW, items[ind].V});
            curW += delW;
            ind++;
        }
    }

    int dp[S + 1];
    fill(dp, dp + S + 1, 0);

    for (int w = 1; w <= S; w++) {
        for (pair<int, int> i : itemList[w]) {
            for (int curI = 0; curI < i.first; curI++) {
                for (curW = S - w; curW >= 0; curW--) {
                    dp[curW + w] = max(dp[curW + w], dp[curW] + i.second);
                }
            }
        }
    }

    cout << *max_element(dp, dp + S + 1) << "\n";
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

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

Subtask #5
0 / 27.0

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