Submission #637550

#	Time	Username	Problem	Language	Result	Execution time	Memory
637550		PagodePaiva	Knapsack (NOI18_knapsack)	C++14	49 / 100	1085 ms	66564 KiB

knapsack

#include<bits/stdc++.h>
// #define int long long
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define sz size
#define ll long long int
#define pi pair <int,int>
#define itn int
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
#define rvs(v) reverse(v.begin(), v.end())
#define mod 1000000007
#define INF 1e6
#define N 100010

using namespace std;

itn n, s;
int v[N], ps[N], qtd[N];
map <pair <int, pi>, int> dp;

int solve(int pos, int peso, int quant){
    if(peso < 0 or quant < 0) return -INF;
    if(pos == 0) return 0;
    // if(quant == 0) return solve(pos-1, peso, qtd[pos-1]);
    if(dp.find({pos, {peso, quant}}) != dp.end()) return dp[{pos, {peso, quant}}];

    // cout << pos << " " << peso << " " << quant << "\n";

    dp[{pos, {peso, quant}}] = max(solve(pos-1, peso, qtd[pos-1]), solve(pos, peso - ps[pos], quant - 1) + v[pos]);

    return dp[{pos, {peso, quant}}];
} 

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> s >> n;

    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> ps[i] >> qtd[i];
        if(qtd[i] > s/ps[i]){
            qtd[i] = s/ps[i];
        }
    }

    solve(n, s, qtd[n]);

    // for(int i = 1;i <= n;i++){
    //     for(int j = 0;j <= s;j++){
    //         cout << dp[{i, {j, qtd[i]}}] << " ";
    //     }

    //     cout << "\n";
    // }

    cout << dp[{n, {s, qtd[n]}}] << "\n";

    return 0;
}

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