Submission #1357462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357462		hollowtimes	Knapsack (NOI18_knapsack)	C++20	73 / 100	132 ms	327680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ll=long long;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int s,n,m=0;
    cin>>s>>n;
    vector<array<int,3>>a(n);
    vector<vector<int>>dp(s+1,vector<int>(n+1));
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    for(int i=1;i<=s;i++){
        for(int j=0;j<n;j++){
            if(i-a[j][1]>=0&&dp[i-a[j][1]][j+1]<a[j][2]){
                if(dp[i-a[j][1]][0]+a[j][0]>dp[i][0]){
                    dp[i]=dp[i-a[j][1]];
                    dp[i][0]+=a[j][0];
                    dp[i][j+1]++;
                    m=max(m,dp[i][0]);
                }
            }
        }
    }
    cout<<m;
    return 0;
}

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