제출 #1096549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096549		Irate	Knapsack (NOI18_knapsack)	C++17	100 / 100	39 ms	2936 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2005;
struct Item{
    int v, w, k;
    bool operator<(Item &other){
        return v > other.v;
    }
};
vector<long long>dp1, dp2;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dp1.assign(MAX, -1e18);
    dp2.assign(MAX, -1e18);
    dp2[0] = 0;
    int n, S;
    cin >> S >> n;
    vector<Item>vv(n);
    for(int i = 0;i < n;++i){
        int v, w, k;
        cin >> v >> w >> k;
        vv[i] = {v, w, k};
    }
    sort(vv.begin(), vv.end());
    vector<vector<int>>items(S + 1);
    for(int i = 0;i < n;++i){
        int v = vv[i].v, w = vv[i].w, k = vv[i].k;
        for(int j = 0;j < min(k, S / w) && (int)items[w].size() + 1 <= S / w;++j){
            items[w].push_back(v);
        }
    }
    for(int i = 1;i <= S;++i){
        for(int j = 0;j <= S;++j){
            long long sum = 0;
            dp1[j] = dp2[j];
            for(int k = 0;k < (int)items[i].size() && j - (k + 1) * i >= 0;++k){
                sum += items[i][k];
                dp1[j] = max(dp1[j], dp2[j - (k + 1) * i] + sum);
            }
        }
        dp2 = dp1;
    }
    long long mx = 0;
    for(int i = 1;i <= S;++i){
        mx = max(mx, dp1[i]);
    }
    cout << mx << '\n';
}

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