Submission #1183494

#TimeUsernameProblemLanguageResultExecution timeMemory
1183494bgnbvnbvKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms2628 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){ for(int l = 1; k[i] > 0; l *= 2){ int rem = min(l,k[i]); for(int j = s;j >= rem * w[i];--j){ dp[j] = max(dp[j],dp[j-rem *w[i]] + rem * v[i]); } k[i] -= rem; } } 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...