Submission #1183479

#TimeUsernameProblemLanguageResultExecution timeMemory
1183479bgnbvnbvKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms2632 KiB
#include <bits/stdc++.h> #define endl '\n' #define ll long long #define pb push_back #define ull unsigned long long #define st first #define nd second #define int long long using namespace std; const int lim = 2e5+1; const ll mod = 1e9+7; const int base = 31; const int maxn = 1e5+5; const int inf = 1e18; main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,s; cin >> s >> n; vector <int> v(n),w(n),k(n); for(int i = 0; i <n;++i){ cin >> v[i] >> w[i]>>k[i]; } vector <int> dp(s+1,0); for(int i=0;i<n;++i){ if(k[i] == 1){ for(int j = s; j >= w[i];--j){ dp[j] = max(dp[j], dp[j -w[i]] + v[i]); } } else if(k[i] < s){ for(int l = 1; l <= k[i];l *= 2){ for(int j = s; j >= l * w[i]; --j){ dp[j] = max(dp[j], dp[j - l * w[i]] + l * v[i]); } k[i] -= l; } if(k[i] > 0){ for(int j = s;j >= k[i] * w[i];--j){ dp[j] = max(dp[j],dp[j- k[i]*w[i]] + k[i]*v[i]); } } } else{ for (int j = w[i]; j <= s; ++j) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } } cout << dp[s] << endl; return 0; }

Compilation message (stderr)

knapsack.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...