Submission #775482

#	Time	Username	Problem	Language	Result	Execution time	Memory
775482		roctes7	Knapsack (NOI18_knapsack)	C++17	0 / 100	84 ms	262144 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;




ll mem[3001][25000];

int dp(int i,int num){
    if(num>s)return -1e9;
    if(i==fin.size())return 0;
    if(mem[i][num]!=-1)return mem[i][num];

    int ans = max(dp(i+1,num),dp(i+1,num+fin[i].fi)+fin[i].se);
    return mem[i][num] = ans;
}

int main(){

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


    memset(mem,-1,sizeof mem);


    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});
            }
        }

    }




    cout<<dp(0,0);


    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int dp(int, int)':
knapsack.cpp:45:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     if(i==fin.size())return 0;
      |        ~^~~~~~~~~~~~

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