Submission #876053

#	Time	Username	Problem	Language	Result	Execution time	Memory
876053		tth	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	2516 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair <ll, ll>
#define foru(i,a,b) for (ll i = a; i <= b; i++)
#define ford(i,a,b) for (ll i = a; i >= b; i--)
#define N int(1e5 + 5)
#define M int(2e3 + 5)
#define MOD int(1e9 + 7)
#define base 311

int n, s;
ll w[N], v[N], k[N], dp[M], tmp[M];

int main()
{
    //freopen("KNAPSACK.inp","r",stdin);
    // freopen("KNAPSACK.out","w",stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> s >> n;
    foru(i, 1, n) cin >> v[i] >> w[i] >> k[i];

    foru(i, 1, s) dp[i] = -1;
    foru(i, 1, n)
    {
        foru(j, 1, s) tmp[j] = 0;

        foru(j, w[i], s)
        {
            if (dp[j - w[i]] == -1) continue;
            if (dp[j] < dp[j - w[i]] + v[i] && tmp[j - w[i]] < k[i])
            {
                dp[j] = dp[j - w[i]] + v[i];
                tmp[j] = tmp[j - w[i]] + 1;
            }
        }
    }

    cout << *max_element(dp, dp+1+s);

    return 0;
}

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