제출 #1096547

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

knapsack

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2005;
struct Item{
    int v, w, k;
    bool operator<(Item &other){
        if(w == other.w)return v > other.v;
        return w < other.w;
    }
};
long long dp[MAX][MAX];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0;i < MAX;++i){
        for(int j = 0;j < MAX;++j){
            dp[i][j] = -1e18;
        }
    }
    dp[0][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;
            dp[i][j] = dp[i - 1][j];
            for(int k = 0;k < (int)items[i].size() && j - (k + 1) * i >= 0;++k){
                sum += items[i][k];
                dp[i][j] = max(dp[i][j], dp[i - 1][j - (k + 1) * i] + sum);
            }
        }
    }
    long long mx = 0;
    for(int i = 1;i <= S;++i){
        mx = max(mx, dp[S][i]);
    }
    cout << mx << '\n';
}

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