제출 #1126479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126479		Icelast	Knapsack (NOI18_knapsack)	C++17	100 / 100	72 ms	6728 KiB

knapsack

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct item{
    ll v, w, k;
};
void solve(){
    int s, n;
    cin >> s >> n;
    vector<item> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].v >> a[i].w >> a[i].k;
    }
    vector<vector<item>> t(s+1);
    for(int i = 1; i <= n; i++){
        t[a[i].w].push_back(a[i]);
    }
    vector<item> b;
    for(int i = 0; i <= s; i++){
        sort(t[i].begin(), t[i].end(), [&](item a, item b){return a.v > b.v;});
        int cnt = 0;
        int j = 0;
        while(j < (int)t[i].size() && cnt < s/i){
            if(t[i][j].k > 0){
                b.push_back(t[i][j]);
                t[i][j].k--;
                cnt++;
            }else{
                j++;
            }
        }
    }
    vector<ll> f(s+1, -INF), prv(s+1, -INF);
    f[0] = 0;
    for(auto it : b){
        prv = f;
        fill(f.begin(), f.end(), -INF);
        for(int j = 0; j <= s; j++){
            f[j] = prv[j];
            if(j-it.w >= 0) f[j] = max(f[j], prv[j-it.w]+it.v);
        }
    }
    ll ans = -INF;
    for(int j = 0; j <= s; j++){
        ans = max(ans, f[j]);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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