Submission #1312431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312431		br1	Knapsack (NOI18_knapsack)	C++20	37 / 100	1095 ms	580 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define rsrt(x) sort(rall(x))
#define sz(x) (int)x.size()
#define fi first
#define se second
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vll>;

const ll inf=1e18;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll s, n; cin>>s>>n;
    vll v(n), w(n), k(n); for(int i=0; i<n; i++) cin>>v[i]>>w[i]>>k[i]; 

    vll dp(s+1); 
    for(int i=0; i<n; i++) for(int x=0; x<k[i]; x++){
        for(int j=s; j>=w[i]; j--){
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }

    cout<<dp[s]<<'\n';
}

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