Submission #1201561

#TimeUsernameProblemLanguageResultExecution timeMemory
1201561spampotsKnapsack (NOI18_knapsack)C++20
17 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpii; const int MOD = 1e9 + 7; const int INF = INT_MAX; const ll LINF = LLONG_MAX; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) v.begin(), v.end() #define rep(i, a, b) for (int i = a; i < b; ++i) void solve() { int s, n; cin >> s >> n; int v[n], w[n], k[n]; rep(i, 0, n) cin >> v[i] >> w[i] >> k[i]; vector<int> dp(s + 1, -INF); dp[0] = 0; for (int i = 0; i < n; ++i) { for (int l = s; l >= 0; --l) { int count = k[i]; for (int power = 1; count > 0; power *= 2) { int j = min(power, count); if (j * w[i] > l) break; dp[l] = max(dp[l], dp[l - j * w[i]] + j * v[i]); count -= j; } } } int ans = 0; for (int i = 0; i <= s; ++i) { ans = max(ans, dp[i]); } cout << ans << endl; } int main() { fast; int t = 1; while (t--) { solve(); } return 0; }
#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...