제출 #672269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672269		Hafiz_	Knapsack (NOI18_knapsack)	C++17	0 / 100	112 ms	262144 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[100005][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;
    //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);
    }
}

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