Submission #1066494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066494		wood	Knapsack (NOI18_knapsack)	C++17	100 / 100	40 ms	2908 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<class T>
using Tree =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
#define int ll


signed main() {
    fast_cin();
    int s, n;
    cin >> s >> n;
    vp32 vp[s+1];
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        vp[w].eb(v, k);
    }
    int dp[s+1];
    fill(dp,dp+s+1,INT_MIN);
    dp[0] = 0;
    for (int i = 1; i <= s; i++) {
        if(vp[i].empty()) continue;
        sort(vp[i].begin(), vp[i].end());
        int weight = i;
        int cur = 0;
        int cnt = 0;
        auto ii = vp[i].rbegin();
        vi res(s+1);
        for(int j = 0; j<=s; j++) res[j] = dp[j];
        while (weight<=s) {
            if (cnt >= ii->se) {
                ii++;
                if(ii==vp[i].rend())break;
                cnt = 0;
            }
            cur+=ii->fi;
            for(int j = 0; j<=s-weight; j++){
                res[j+weight] = max(res[j+weight],dp[j]+cur);
            }
            cnt++;
            weight += i ;
        }
        for(int j = 0; j<=s; j++) dp[j] = res[j];
    }
    for(int i = 1; i<=s; i++){
        dp[i] = max(dp[i],dp[i-1]);
    }
    cout<<dp[s]<<'\n';
    return 0;
}

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