Submission #541673

#	Time	Username	Problem	Language	Result	Execution time	Memory
541673		Aanjaney	Knapsack (NOI18_knapsack)	C++17	73 / 100	149 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MODA 998244353
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sorta(A, N) sort(A, A + N)
#define debug(x) cerr << #x << " is " << x;
#define rep(i, a, N) for (ll i = a; i < N; i++)
#define f first
#define s second
#define uniq(v)                                       \
    {                                                 \
        sort(v.begin(), v.end());                     \
        v.erase(unique(v.begin(), v.end()), v.end()); \
    }
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
void solve(ll tcase)
{
    ll S, N, maxi = 0;
    cin >> S >> N;
    ll dp[N + 1][S + 1];
    ll V[N + 1], W[N + 1], K[N + 1];
    memset(dp, 0, sizeof(dp));
    rep(i, 1, N + 1) cin >> V[i] >> W[i] >> K[i];
    rep(n, 1, N + 1)
    {
        rep(w, 1, S + 1)
        {
            rep(k, 0, K[n] + 1)
            {
                if (w - k * W[n] < 0)
                    break;
                dp[n][w] = max(dp[n][w], dp[n - 1][w - k * W[n]] + k * V[n]);
            }
            maxi = max(maxi, dp[n][w]);
        }
    }
    cout << maxi;
}
int main()
{
    speed;
    ll t = 1;
    rep(i, 1, t + 1)
        solve(i);
}

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