Submission #1312692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312692		br1	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	440 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 dp(s+1);
    auto update = [&](ll ww, ll vv){
        for(ll j=s; j>=ww; j--) 
            dp[j] = max(dp[j], dp[j-ww]+vv);
    };
    
    for(int i=0; i<n; i++) {
        ll c=1, v, w, k;
        cin>>v>>w>>k;
        while(k>c){
            k-=c;
            update(c*w, c*v);
            c*=2;
        }
        update(k*w, k*v);
    }

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

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