제출 #1359221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359221		atif2077	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	1092 KiB

knapsack

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

ll f(ll i, ll s, ll& n, vector<vector<ll>>& a, vector<vector<int>>& dp)
{
    if (i == n) return 0;
    if (s < 0) return (ll) -1e18;

    if (dp[i][s] != -1) return dp[i][s];

    ll pick = 0;
    ll noPick = 0;

    if (a[i][2]) 
    {
        a[i][2]--;
        pick = a[i][0] + f(i, s - a[i][1], n, a, dp);
        a[i][2]++;
    }
    noPick = f(i + 1, s, n, a, dp);

    return dp[i][s] = max(pick, noPick);
}

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

    ll s, n;
    cin >> s >> n;

    vector<vector<ll>> a(n, vector<ll> (3, 0));

    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < 3; j++)
        {
            cin >> a[i][j];
        }
    }

    vector<vector<int>> dp(n + 1, vector<int> (s + 5, -1));
    cout << f(0, s, n, a, dp);

    return 0;
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 0 / 17
• 서브태스크 3: 0 / 20
• 서브태스크 4: 0 / 24
• 서브태스크 5: 0 / 27