Submission #701150

#	Time	Username	Problem	Language	Result	Execution time	Memory
701150		thimote75	Knapsack (NOI18_knapsack)	C++14	100 / 100	110 ms	4324 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define num long long

const int MAX_S = 2002;

struct Object {
    int W, V, K;

    Object () = default;
    void scan () {
        cin >> V >> W >> K;
    }

    bool operator< (const Object &other) const {
        return V > other.V;
    }
};

struct ElementArray {
    vector<Object> objects;

    void _sort () {
        sort(objects.begin(), objects.end());
    }
    void iterate (int max_iter, void (*f)(int, int)) {
        int idx = 0;

        for (Object obj : objects) {
            for (int k = 0; k < obj.K; k ++) {
                f(obj.W, obj.V);

                idx ++;
                if (idx >= max_iter) return ;
            }
        }
    }
};

ElementArray objects[MAX_S];

void create () {
    Object obj;
    obj.scan();
    
    objects[obj.W].objects.push_back(obj);
}

num dp[MAX_S];

void apply (int weight, int value) {
    for (int idx = MAX_S - 1 - weight; idx >= 0; idx --)
        dp[idx + weight] = max(dp[idx + weight], dp[idx] + value);
}

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

    for (int idx = 0; idx  < N; idx ++) create();
    for (int idx = 0; idx <= S; idx ++) objects[idx]._sort();

    for (int idx = 1; idx <= S; idx ++)
        objects[idx].iterate(S / idx, apply);
    
    cout << dp[S];
}

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