Submission #944211

#	Time	Username	Problem	Language	Result	Execution time	Memory
944211		Samiul2651	Knapsack (NOI18_knapsack)	C++17	73 / 100	166 ms	262144 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;
    std::vector<pii> v[s+1];
    vector<pair<double, int>> x(n);
    vector<array<int, 3>> y(n);
    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(v[w].size() < sz && j < k){
                v[w].push_back({price, w});
                j++;
            }
        }
    }
    vector<pii> V;
    for(int i = 0;i <= s;i++){
        for(auto [v, w] : v[i]){
            V.push_back({v,w});
        }
    }
    int dp[sz(V)+5][s+5];
    memset(dp, 0, sizeof(dp));
    for(int i = 1;i <= sz(V);i++){
        int val = V[i-1].first;
        int w = V[i-1].second;
        //cout << val << " " << w << nl;
        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(long long int)':
knapsack.cpp:45:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |             while(v[w].size() < sz && j < k){
      |                   ~~~~~~~~~~~~^~~~

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