Submission #944218

#	Time	Username	Problem	Language	Result	Execution time	Memory
944218		Samiul2651	Knapsack (NOI18_knapsack)	C++14	100 / 100	243 ms	142812 KiB

knapsack

#include <bits/stdc++.h>
#include <numeric>
#define nl "\n"
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
//#define int long long
#define sz(v) (int)v.size()
#define clearAll(v, n) for(int i = 0;i < n;i++)v[i].clear()
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef __gnu_pbds::tree<long long, __gnu_pbds::null_type, less<long long>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;
 
double pi = 2*acos(0.0);
const ll MAXN = 1e5 + 5;
const ll mod = 998244353;
//const int inf = LLONG_MAX;



void solve(int ca){
    int s, n;
    cin >> s >> n;
    vector<pair<double, int>> x(n);
    vector<array<int, 3>> y(n);
    int cnt[s+1] = {0};
    vector<pii> v;
    for(int i = 0;i < n;i++){
        cin >> y[i][0] >> y[i][1] >> y[i][2];
        x[i] = {((double)y[i][0]/(double)y[i][1]), i};
    }
    sort(rall(x));
    for(int i = 0;i < n;i++){
        int idx = x[i].second;
        int price = y[idx][0];
        int w = y[idx][1];
        int k = y[idx][2];
        if(w <= s){
            int j = 0;
            int sz = s/w + 1;
            while(cnt[w] < sz && j < k){
                v.push_back({price, w});
                j++;
                cnt[w]++;
            }
        }
    }
    int dp[sz(v)+5][s+5];
    memset(dp, 0, sizeof(dp));
    int i = 0;
    for(int i = 1;i <= sz(v);i++){
        int val = v[i-1].first;
        int w = v[i-1].second;
        for(int j = 1;j <= s;j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(w <= j){
                dp[i][j] = max(dp[i][j], (dp[i-1][j-w] + val));
            }
        }
    
        //cout << dp[i][5] << nl; 
    }
    cout << dp[sz(v)][s] << nl;
}


int32_t main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
   // freopen("time.in","r",stdin);
   // freopen("time.out","w",stdout);
    
    
    ll t = 1;
    // cin >> t;
    ll i = 1;
    while(t--){
        solve(i);
        i++;
    }
 
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve(int)':
knapsack.cpp:55:9: warning: unused variable 'i' [-Wunused-variable]
   55 |     int i = 0;
      |         ^

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