Submission #862847

#	Time	Username	Problem	Language	Result	Execution time	Memory
862847		dead0ne	Knapsack (NOI18_knapsack)	C++17	100 / 100	406 ms	250576 KiB

knapsack

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000009
#define lim 200005
using namespace std;




vii fin;
int dp[20005][2005];


int calc(int unt, int left){
    if(dp[unt][left]!=-1) return dp[unt][left];
    dp[unt][left] = calc(unt-1, left);
    if(left - fin[unt].nd >= 0) dp[unt][left] = max(dp[unt][left], calc(unt-1, left - fin[unt].nd) + fin[unt].st);
    return dp[unt][left];
}




void solve(){
    int s,n; cin >> s >> n;
    vii wei[s+1];
    for(int i=1; i<=n; i++){
        int v,w,k; cin >> v >> w >> k;
        wei[w].pb({v,k});
    }

    fin.pb({-1,-1});
    for(int i=1; i<=s; i++){
        sort(all(wei[i]), greater<pair<int, int>>());
        int cnt=0;
        for(int j=0; j<wei[i].size() && cnt<s/i; j++){
            for(int k=1; k<=wei[i][j].nd && cnt<s/i; k++){
                fin.pb({wei[i][j].st, i});
                cnt++;
            }
        }
    }

    for(int i=0; i<=fin.size(); i++) for(int j=0; j<=s; j++) dp[i][j]=-1;
    for(int j=0; j<=s; j++) dp[0][j] = 0;
    cout << calc(fin.size()-1, s) << endl;
}


signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif

    int t=1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:48:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j=0; j<wei[i].size() && cnt<s/i; j++){
      |                      ~^~~~~~~~~~~~~~
knapsack.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0; i<=fin.size(); i++) for(int j=0; j<=s; j++) dp[i][j]=-1;
      |                  ~^~~~~~~~~~~~

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