Submission #1333973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333973		veyis_112	Knapsack (NOI18_knapsack)	C++20	29 / 100	16 ms	656 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
int main(){
    ll n,s1; cin>>s1>>n; vector<pair<ll,ll>>v;
    ll k1;
    for(ll i=0;i<n;i++){
            ll v1,w;
        cin>>v1>>w>>k1;
        v.push_back({v1,w});
    }
    if(n==1){
    ll d=min(k1,s1/v[0].s);
    cout<<d*v[0].first; return 0;
    }
    if(k1==1){
        map<ll,ll>pul,ceki;
        ceki[0]=1;
        for(ll i=0;i<n;i++){
            for(ll j=s1;j>=v[i].s;j--){
                if(ceki[j-v[i].s]){
                    ceki[j]=1;
                    pul[j]=max(pul[j],pul[j-v[i].s]+v[i].f);
                }
            }
        }
        ll maxi=-1e18;
        for(ll i=0;i<=s1;i++){
            maxi=max(maxi,pul[i]);
        }
        cout<<maxi<<endl;
    }

}

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