Submission #1139058

#TimeUsernameProblemLanguageResultExecution timeMemory
1139058ndanKnapsack (NOI18_knapsack)C++20
73 / 100
1092 ms2824 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define forr(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define ford(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define forf(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define file "test" const int maxn = 1e6 + 5; ll s, n, v[maxn], w[maxn], k[maxn]; namespace sub1 { bool check() { return n == 1; } void solve() { cout << v[1] * min(s / w[1], k[1]); } } namespace sub2 { bool check() { if (n > 100) return 0; forr(i, 1, n) if (k[i] > 1) return 0; return 1; } void solve() { ll dp[2005]; memset(dp, 0, sizeof dp); forr(i, 1, n) ford(j, s, w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); cout << dp[s]; } } namespace sub3 { bool check() { if (n > 100) return 0; forr(i, 1, n) if (k[i] > 10) return 0; return 1; } void solve() { ll dp[2005]; memset(dp, 0, sizeof dp); forr(i, 1, n) ford(j, s, w[i]) forr(sl, 1, min(k[i], j / w[i])) dp[j] = max(dp[j], dp[j - w[i] * sl] + v[i] * sl); cout << dp[s]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); cin >> s >> n; forr(i, 1, n) cin >> v[i] >> w[i] >> k[i]; if (sub1::check()) sub1::solve(); else if (sub2::check()) sub2::solve(); else sub3::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...