Submission #577264

#	Time	Username	Problem	Language	Result	Execution time	Memory
577264		leroycut	Knapsack (NOI18_knapsack)	C++17	29 / 100	2 ms	332 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int mod = 1000000007, N = 2003, inf = 1000000007;

int dp[N];

struct node{
    int v, w, k;
};

bool cnt(node a, node b){
    return a.v * b.w * 1ll < a.w * b.v * 1ll;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);

    for(int i = 0; i < N; ++i){
        dp[i] = 0;
    }

    int s, n;

    cin >> s >> n;

    vector<node> v(n);

    for(int i = 0; i < n; ++i){
        cin >> v[i].v >> v[i].w >> v[i].k;
    }

    sort(v.begin(), v.end(), cnt);

    // for(int i = 0; i < n; ++i) {
    //     cout << v[i].w << " ";
    // }

    for(int i = 0; i < n; ++i){
        for(int j = s; j > 0; --j){
            int cou = j / v[i].w;
            cou = min(cou, v[i].k);
            dp[j] = max(dp[j], dp[j - v[i].w * cou] + v[i].v * cou);
        }
    }

    cout << dp[s];
}

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