Submission #775486

#	Time	Username	Problem	Language	Result	Execution time	Memory
775486		roctes7	Knapsack (NOI18_knapsack)	C++17	100 / 100	72 ms	3972 KiB

knapsack

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be begin()
#define en end()
#define pb push_back
#define mpa make_pair
#define pii pair<int, int>
typedef long long ll;
typedef long double ld;
const int MAX = 1e6 + 13;
const ld eps = 1e-7;
ll INF = 1e18;
const int mod = 1e9 + 7;
//const int mod = 998244353;



int s,n;


vector<pii> v_k[2002];
vector<pii> fin;




int mem[25000];
int curmem[25000];


int main(){

    fastio;
    //freopen("snakes.in","r",stdin);
    //freopen("snakes.out","w",stdout);



    cin>>s>>n;

    for (int i=0;i<n;i++){
        int w,v,k;
        cin>>v>>w>>k;
        v_k[w].pb({v,k});
    }


    for(int i=1;i<=s;i++){
        sort(v_k[i].rbegin(),v_k[i].rend());
    }

    for (int i=1;i<=s;i++){
        int cnt = 0;
        for(auto a:v_k[i]){
            int num = a.se;
            int pr = a.fi;

            while(num>0&&cnt<=s/i+1){
                num--;
                cnt++;
                fin.pb({i,pr});
            }
        }

    }



    for (int i=fin.size()-1;i>=0;i--){
        for (int num = 0;num<=s;num++){
                curmem[num] = mem[num];
                if(num+fin[i].fi<=s)curmem[num] = max(mem[num],mem[num+fin[i].fi] + fin[i].se);
        }

        for (int num = 0;num<=s;num++){
                 mem[num] = curmem[num];
                 curmem[num] = 0;
        }
    }


    cout<<mem[0];


    return 0;
}

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