Submission #922002

#	Time	Username	Problem	Language	Result	Execution time	Memory
922002		Pikachu0123	Knapsack (NOI18_knapsack)	C++17	73 / 100	1050 ms	7500 KiB

knapsack

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
// for changing to descending, change less<pair<int,int>> to greater<pair<int,int>>

const int primeNo = 999999929;

#define int long long
#define pb push_back
#define endl "\n"
#define vi vector<int>
#define pii pair<int,int>
#define sz(x) ((int) x.size())
#define all(p) p.begin(), p.end()
#define yes() cout<<"YES"<<endl
#define no() cout<<"NO"<<endl
#define rep(i, l, r) for(int i = l; i<r; i++)
#define vvi vector<vector<int>>
#define INF LLONG_MAX
#define ff first
#define ss second
#define print(a) for(auto x : a) cout << x << " "; cout << endl
#define ppb pop_back
#define float double
#define double long double
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int32_t main(){
    fastio();
    
    int wt, n;
    cin >> wt >> n;

    vector<vector<int>> v;
    for(int i=0; i<n; i++){
        int a, b, c;
        cin >> a >> b >> c;

        v.push_back({a,b,c});
    }

    vector<int> dp(wt+1, 0);

    for(int i=0; i<n; i++){
        for(int j=wt; j>=0; j--){
            int p = 1;
            while(j + p*v[i][1] <= wt and p <= v[i][2]){
                int k = j + p * v[i][1];
                dp[k] = max(dp[k], dp[j] + p*v[i][0]);
                p++;
            }
        }
    }

    cout << dp[wt] << endl;

    return 0;
}

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