Submission #852195

#	Time	Username	Problem	Language	Result	Execution time	Memory
852195		daoda	Knapsack (NOI18_knapsack)	C++17	100 / 100	61 ms	4956 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define FOR(a, b) for(ll i = a; i < b; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long int ll;
typedef pair<ll, ll> pll; // comments that are mixed
typedef vector<ll> vll; // in with code are placed
typedef vector<pll> vpll; // on the right side
typedef vector<bool> vb;
typedef vector<char> vc;

struct item {
  ll v, w, k;  
};

bool cmp(item& a, item& b) {
    if(a.w == b.w) return a.v > b.v;
    return a.w < b.w;
}

int main() {
    fast
    
    ll s, n;
    cin >> s >> n;

    vll dp(s + 1, -1);
    dp[0]=0;
    vector<item> items(n);
    FOR(0, n) cin >> items[i].v >> items[i].w >> items[i].k;
    sort(items.begin(), items.end(), cmp);

    ll amt=s, cur_w=1;

    FOR(0, n) {
        if(items[i].w < cur_w) continue;
        if(items[i].w > cur_w) {
            cur_w=items[i].w;
            amt=s / cur_w;
        }
        
        for(ll i2=0; i2 < items[i].k; i2++) {
            for(ll i3=s; i3 >= cur_w; i3--) {
                if(dp[i3 - cur_w] >= 0) dp[i3] = max(dp[i3], dp[i3 - cur_w] + items[i].v) ;
            }
            
            amt--;    
            if(!amt) {
                cur_w++;
                amt=s / cur_w;
                break;
            }
        }
    }

    ll ans=0;
    FOR(1, s + 1) ans=max(ans, dp[i]);
    cout << ans;

    return 0;
}

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