Submission #791218

#	Time	Username	Problem	Language	Result	Execution time	Memory
791218		AmrT	Knapsack (NOI18_knapsack)	C++17	49 / 100	99 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
#define lop(i,a,b) for(ll i = a; i < b; i++)
#define alop(i,v) for(auto &i: v)
#define in(v) for(auto &i: v) cin >> i;
#define ll long long
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(dp, x) memset(dp, x, sizeof(dp))
#define F first
#define S second
using namespace std;
ll mod = 2019;
const ll N = 1e5;

ll fpow(ll x, ll p){
    if(p == 0) return 1;
    if(p == 1) return x % mod;
    ll result = 1;
    if((p & 1) == 1) result = x % mod, p--;
    ll h = fpow(x, (p >> 1)) % mod;
    result *= (h * h) % mod;
    return result % mod;
}

signed main()
{
    int n, s; cin >> s >> n;
    vector<array<ll, 3>> v(n); // {value, weight, copies}
    vector<pair<ll, ll>> arr(1);
    alop(i, v){
        in(i);
        ll temp = s / i[1] + 1;
        for(int j = 1; (j <= temp && j <= i[2]); j++) arr.pb({i[1], i[0]});
    }

    n = arr.size() - 1;
    ll dp[n + 1][s + 1] = {};

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= s; j++){
            dp[i][j] = dp[i - 1][j];
            if(j - arr[i].first >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i].first] + arr[i].second);
        }
    }
    cout << dp[n][s];

    return 0;
}

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