Submission #1040437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040437		Aureum	Knapsack (NOI18_knapsack)	C++17	0 / 100	19 ms	50012 KiB

knapsack

/*
o((>ω< ))o
o(≧口≦)o
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define int ll
#define F first
#define S second
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
//#define endl "\n"
struct mrbeast{
    int v; int w; int k;
};
struct roblox{
    int w; int v;
};
void solve(){
    int S,n,m;
    cin >> S >> n;
    vector<mrbeast> a_(1e5+10);
    vector<roblox> a(3000);
    vector<vector<int>> dp(3000,vector<int>(2005));
    for (int i = 1; i <= n; i++) cin >> a_[i].v >> a_[i].w >> a_[i].k;

    m = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; (1 << j) <= a_[i].k; j++){
            a[++m].w = a_[i].w*(1<<j);
            a[m].v = a_[i].v*(1<<j);
        }
    }
    // cout << endl;
    // for (int i = 1; i <= m; i++) cout << a[i].w << ' ' << a[i].v << endl;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= S; j++){
            dp[i][j] = dp[i-1][j];
            if (a[i].w < j){
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
            }
        }
    }
    cout << dp[n][S] << endl;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // int t; cin >> t; while (t--)
    solve();
}

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