Submission #998539

#	Time	Username	Problem	Language	Result	Execution time	Memory
998539		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	33 ms	6488 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 5;
int n,s;
int f[2005];
struct p{
    int v,w,k;
};
p a[N];
vector<int> dsk[2005];
ii arr[N];
bool cmp(int i,int j){
    return a[i].v > a[j].v;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>> s>> n;
    for(int i = 1; i <= n; i++){
        cin>> a[i].v>> a[i].w>> a[i].k;
        a[i].k = min(a[i].k,s);
        dsk[a[i].w].push_back(i);
    }
    int dem = 0;
    for(int i = 1; i <= s; i++){
        int sl = 0;
        sort(dsk[i].begin(),dsk[i].end(),cmp);
        for(int j : dsk[i]){
            sl += a[j].k;
            int _sl = 1;
            while(_sl <= a[j].k){
                a[j].k -= _sl;
                arr[++dem] = {_sl*a[j].v,_sl*a[j].w};
                _sl*=2;
            }
            if(a[j].k > 0){
                arr[++dem] = {a[j].v*a[j].k,a[j].w*a[j].k};
            }
            if(sl*i > s)    break;
        }

    }
    int tons = 0;
    int ans = 0;
    for(int i = 1; i <= dem; i++){
        tons += arr[i].se;
        for(int j = min(s,tons); j >= arr[i].se; j--){
            f[j] = max(f[j],f[j-arr[i].se] + arr[i].fi);
            ans = max(ans,f[j]);
        }
    }
    cout<<ans;
}

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