제출 #577331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577331		leroycut	Knapsack (NOI18_knapsack)	C++17	100 / 100	64 ms	4888 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;
};

vector<vector<pair<int, int>>> vv;


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);
    vector<pair<int, int>> a;
    vv.resize(2003);

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

    for(int i = 0; i < N; ++i){
        sort(vv[i].begin(), vv[i].end());
    }

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


    for(int i = 1; i <= s; ++i){
        if(vv[i].size() == 0) continue;
        int sz = vv[i].size();

        for(int w = s; w > 0; --w){
            int cou = 1, val = 0;
            for(int j = sz - 1; j >= 0 && cou * i <= w; --j){
                int couj = 0;
                while(vv[i][j].second > couj && cou * i <= w){
                    couj++;
                    val += vv[i][j].first;
                    dp[w] = max(dp[w], dp[w - i * cou] + val);
                    cou++;
                }
            }
        }
    }

    // for(int i = 0; i <= s; ++i){
    //     cout << dp[i] << " ";
    // }

    cout << dp[s];
}

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