Submission #1200478

#TimeUsernameProblemLanguageResultExecution timeMemory
1200478spampotsKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms1608 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) { for (int j = 1; j <= k[i] && j * w[i] <= l; ++j) { if (dp[l - j * w[i]] != -INF) { dp[l] = max(dp[l], dp[l - j * w[i]] + j * v[i]); } } } } for(int i = 1; i <= s; ++i){ dp[i] = max(dp[i], dp[i-1]); } cout << dp[s] << 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...