Submission #499928

#	Time	Username	Problem	Language	Result	Execution time	Memory
499928		AnYandEvery	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	296 KiB

knapsack

/*
NOI: https://oj.uz/problem/view/NOI18_knapsack
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//idea 1: Ki beyond 2000 is the same as Ki of 2000
struct product{
    int worth; int weight; int num;
    void init(int w, int w2, int n){
        worth = w;
        weight = w2;
        num = n;
    }
};
//n<=1e5, ki <= 1e9, s <= 2000
int main(){
    int s, n; cin >> s >> n;
    product products[n];
    for(int i = 0; i < n; i++){
        int a, b, c; cin >> a >> b >> c;//worth, weight, numCopies 
        if(c>2000)c=2000;
        product temp; temp.init(a, b, c);
        products[i] = temp;
    }
    ll dp[s+1]; for(auto & i : dp)i = 0;
    for(int i = 0; i < n; i++){
        int numUse[s+1]; for(auto & zaa : numUse)zaa = 0;
        for(int x = 0; x < s; x++){
            int curW = products[i].weight + x;
            if(curW > s)continue;
            if(dp[x]==0&&x!=0)continue;
            if(numUse[x] == products[i].num)continue;
            ll cur = dp[x] + products[i].worth;
            ll prev = dp[curW];
            if(cur > prev){
                numUse[curW] = numUse[x] + 1;
                dp[curW] = cur;
            }
            if(cur == prev){
                numUse[curW] = min(numUse[x]+1, numUse[curW]);
            }
        }
    }
    ll mx = 0;
    for(auto & i : dp){
        if(i > mx)mx = i;
    }
    cout << mx << endl;
}

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