제출 #1201576

#제출 시각아이디문제언어결과실행 시간메모리
1201576spampotsKnapsack (NOI18_knapsack)C++20
73 / 100
1095 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; vector<int> dp(s + 1, 0); for (int i = 0; i < n; ++i) { int v, w, k; cin >> v >> w >> k; if (1LL * k * w >= s) { // Unbounded knapsack for (int j = w; j <= s; ++j) dp[j] = max(dp[j], dp[j - w] + v); } else { // Bounded knapsack with binary trick for (int c = 1; k > 0; c <<= 1) { int cnt = min(c, k); int wt = cnt * w; int val = cnt * v; for (int j = s; j >= wt; --j) dp[j] = max(dp[j], dp[j - wt] + val); k -= cnt; } } } int ans = *max_element(dp.begin(), dp.end()); cout << ans << "\n"; } 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...