Submission #1040790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040790		Aureum	Knapsack (NOI18_knapsack)	C++17	73 / 100	66 ms	102056 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_[i].k -= (1 << j);
            a[++m].w = a_[i].w*(1<<j);
            a[m].v = a_[i].v*(1<<j);
        }
        if (a_[i].k > 0){
            a[++m].w = a_[i].w*a_[i].k;
            a[m].v = a_[i].v*a_[i].k;
        }
    }
    /*
    cout << endl;
    for (int i = 1; i <= m; i++) cout << a[i].w << ' ' << a[i].v << endl;
    */

    for (int i = 1; i <= m; 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 << "-----------" << endl;
    for (int i = 1; i <= m; i++){
        for (int j = 0; j <= S; j++){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "-----------" << endl;
    */
    cout << dp[m][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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27