Submission #556501

#	Time	Username	Problem	Language	Result	Execution time	Memory
556501		Cookie	Knapsack (NOI18_knapsack)	C++14	73 / 100	176 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
ifstream fin("snakes.in");
ofstream fout("snakes.out");
#include<fstream>
#define pb push_back
#define dq deque
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
struct th{
    ll v, w, k;
};
bool cmp(th a, th b){
    if(a.w != b.w){
        return(a.w < b.w);
    }else{
        return(a.v > b.v);
    }
}
int main()
{
 // normal dp knapsack
 // but for each object of the same weight, sort them in decreasing value and record how much each reached. Greedy
 // Time complexity: o(n * s + slogs)
 int s, n; cin >> s >> n;
 vt<th>v;
 for(int i = 0; i < n; i++){
     ll vv, w, k; cin >> vv >> w >> k;
     v.pb({vv, w, k});
 }
 
   ll dp[n + 1][s + 1];
   memset(dp, 0, sizeof(dp));
   for(int i = 0; i <= n; i++){
       for(int j = 0; j <= s; j++){
           if(j == 0 || i == 0)dp[i][j] = 0;
           else if(j < v[i - 1].w)dp[i][j] = dp[i - 1][j];
           else{
               dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
               ll cr = min(j / v[i - 1].w, v[i - 1].k);
               //cout << cr << " ";
               for(int l = 1; l <= cr; l++){
                   dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1].w * l] + v[i - 1].v * l);
               }
           }
           //cout << dp[i][j] << " ";
       }
      // cout << "\n";
   }
   cout << dp[n][s];
   
   return 0;
}

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