Submission #1120171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120171		vjudge1	Knapsack (NOI18_knapsack)	C++17	37 / 100	283 ms	262144 KiB

knapsack

          /////////////////////////////////////////////////////////////////
         ////////            Born_To_Laugh - Hughie Do            ////////
        /////////////////////////////////////////////////////////////////
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=3e5+5;
const int INF=1e9+7;
/*
    Idea:
*/
void solve(){
    int t ,s;
    cin >> s >> t;
    vector<pair<int,int>> items;
    items.push_back({0,0});
    int n=0;
    while(t--){
        int w, v ,k;
        cin >> v >> w >> k;
        if(w<=s){
            n+=k;
            while(k--){
                items.push_back({w,v});
            }
        }
    }
    sort(items.begin(), items.end());
    vector<vector<int>> dp(n+1, vector<int> (s+1, 0));
    /*
        dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
    */
    dp[0][0]=0;
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=s; ++j){
            if(j-items[i].first >= 0){
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-items[i].first] + items[i].second);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout << dp[n][s];

}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

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