Submission #633464

#	Time	Username	Problem	Language	Result	Execution time	Memory
633464		Iwanttobreakfree	Knapsack (NOI18_knapsack)	C++17	0 / 100	1086 ms	340 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define int long long
bool cmp(pair<int,pair<int,int>>& a,pair<int,pair<int,int>>& b){
    return a.second.first*b.second.second<b.second.first*a.second.second;
}
signed main(){
    long long n,s,x,v,k;
    cin>>s>>n;
    vector<long long> dp(s+1);
    dp[0]=1;
    vector<pair<int,pair<int,int>>> elements(n);
    for(int i=0;i<n;i++){
        cin>>v>>x>>k;
        elements[i]={k,{x,v}};
        k=min(k,s/x);
    }
    sort(elements.begin(),elements.end(),cmp);
    int cur=1;
    set<int> pos;
    for(int i=1;i<=s;i++)pos.insert(-i);
    for(int i=0;i<n;i++){
        for(int j=1;j<=elements[i].first;j++){
            set<int> del;
            for(auto w:pos){
                //cout<<-w<<' '<<elements[i].second.first<<' '<<dp[-w-elements[i].second.first]<<'\n';
                if(-w>=elements[i].second.first&&dp[-w-elements[i].second.first]){
                    dp[-w]=dp[-w-elements[i].second.first]+elements[i].second.second;
                    del.insert(w);
                }
            }
            for(int w:del)pos.erase(w);
        }
    }
    long long ans=0;
    for(int i=0;i<=s;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans-1;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:22:9: warning: unused variable 'cur' [-Wunused-variable]
   22 |     int cur=1;
      |         ^~~

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