Submission #633140

#	Time	Username	Problem	Language	Result	Execution time	Memory
633140		Iwanttobreakfree	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	212 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
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}};
    }
    sort(elements.begin(),elements.end(),cmp);
    int cur=1;
    for(int i=0;i<n;i++){
        //cout<<elements[i].second.first<<' '<<elements[i].second.second<<'\n';
        int cnt=0,cnt2=0;
        while(cnt<=s&&cnt2<elements[i].first&&cur<=s){
            cnt+=elements[i].second.first;
            cnt2++;
            for(int j=s;j>=max(cur,elements[i].second.first);j--){
                //cout<<dp[j-elements[i].second.first]<<' ';
                if(dp[j-elements[i].second.first]){
                    cur=max(cur,j+1);
                    dp[j]=max(dp[j],dp[j-elements[i].second.first]+elements[i].second.second);
                }
            }
        }
    }
    long long ans=0;
    for(int i=0;i<=s;i++){
        ans=max(ans,dp[i]);
        //cout<<dp[i]<<' ';
    }
    cout<<ans-1;
}

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