Submission #1335417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335417		atombulul	Knapsack (NOI18_knapsack)	C++17	73 / 100	1091 ms	456 KiB

knapsack

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

#define ll long long

const int MAXS = 2005;

ll dp[MAXS];

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

    int S,N;
    cin >> S >> N;

    for(int i=1;i<=N;i++){
        ll V,W,K;
        cin >> V >> W >> K;

        if(W > S) continue;
 
        if(W * K >= S){
            for(int j=W;j<=S;j++)
                dp[j] = max(dp[j], dp[j-W] + V);
        }
        else{
 
            ll p = 1;
            while(K > 0){
                ll take = min(p,K);
                ll weight = take * W;
                ll value = take * V;

                for(int j=S;j>=weight;j--)
                    dp[j] = max(dp[j], dp[j-weight] + value);

                K -= take;
                p <<= 1;
            }
        }
    }

    ll res = 0;
    for(int i=0;i<=S;i++) res = max(res, dp[i]);

    cout << res << '\n';
}

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