Submission #672277

#	Time	Username	Problem	Language	Result	Execution time	Memory
672277		Hafiz_	Knapsack (NOI18_knapsack)	C++17	29 / 100	62 ms	157352 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define debug(x) cout<<":["<<x<<"XE]"<<endl;
#define debug2(x,y) cout<<":["<<x<<" "<<y<<"XE]"<<endl;
#define _ ios_base::sync_with_stdio(false);
#define mod 1000000007
#define mod2 998244353
#define inf LLONG_MAX
#define yes cout << "YES\n"
#define yes2 cout << "Yes\n"
#define no cout << "NO\n"
#define no2 cout << "No\n"

ll n,s;
ll v[100005];
ll w[100005];
ll q[100005];
ll dp[10005][2005];

ll sol(ll idx,ll sum)
{
    if(idx>n){
        return 0;
    }
    if(dp[idx][sum]!=-1)return dp[idx][sum];

    ll x=0,y=0;
    for(int i=1;i<=q[idx];i++){
        if(sum+i*w[idx]>s)break;
        x=sol(idx+1,sum+i*w[idx])+v[idx]*i;
    }
    y=sol(idx+1,sum);
    return dp[idx][sum]=max(x,y);
}

int main()
{_
//    freopen("feast.in", "r", stdin);
//    freopen("feast.out", "w", stdout);
    ll t=1,ca=1;
    //cin>>t;
    ///CHECK FROM HERE***
    while(t--){
        //ll n,s;
        cin>>s>>n;
        for(int i=1;i<=n;i++){
            cin>>v[i]>>w[i]>>q[i];
        }
        memset(dp,-1,sizeof dp);
        cout<<sol(1,0);
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:12: warning: unused variable 'ca' [-Wunused-variable]
   42 |     ll t=1,ca=1;
      |            ^~

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