Submission #891021

#	Time	Username	Problem	Language	Result	Execution time	Memory
891021		nikhilg2121	Knapsack (NOI18_knapsack)	C++17	73 / 100	1084 ms	4056 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;
 
#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define mp make_pair
 
 
void solve(){
     int s,n;
     cin>>s>>n;
     vi v(n);
     vi w(n);
     vi k(n);
    fori(i,n){
        cin>>v[i]>>w[i]>>k[i];
    }
    map<int, vii> m;
    fori(i,n){
        if(w[i]>s){
            continue;
        }
        m[w[i]].pb({v[i],k[i]});
    }
    vvi dp(2,vi(s+1,0));
    int h = m.size();
       
        int l=1;
        int i=0;
        for(auto x:m){
            int wt = x.fi;
            // cout<<wt<<" c";
            l=!l;
            rep(j,1,s){
                dp[!l][j] = dp[l][j];
                vii temp = m[wt];
                int resw=0,resv=0,t=1,p=0,curr=0;
                sort(all(temp),greater<pii>());
                while(j-t*wt>=0 && p<sz(temp)){
                    dp[!l][j] = max( dp[!l][j], dp[l][j-t*wt] + resv + temp[p].fi);
                    resv+=temp[p].fi;
                    curr++;
                    if(curr==temp[p].se){
                        curr=0;
                        p++;
                    }
                    t++;
                    // cout<<resv<<" ";
                }
                // fori(p,sz(temp)){
                //     int t=0;
                //     if(j-resw<0){
                //         break;
                //     }
                //     while(t<=temp[p].se && j-t*wt-resw>=0){
                //         dp[!l][j] = max( dp[!l][j], dp[l][j-t*wt-resw] + resv+t*temp[p].fi);
                //         t++;
                //     }
                //     resw+=(t-1)*wt;
                //     resv+=(t-1)*temp[p].fi;
                // }
                // cout<<dp[!l][j]<<"x"<<j<<" ";
            }
            cout<<endl;
            i++;
        }
        int ans=0;
        fori(i,s+1){
            ans = max(ans,dp[h%2][i]);
        }
        // fori(i,n+1){
        //     fori(j,s+1){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        cout<<ans<<endl;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:57:21: warning: unused variable 'resw' [-Wunused-variable]
   57 |                 int resw=0,resv=0,t=1,p=0,curr=0;
      |                     ^~~~

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