Submission #1200476

#TimeUsernameProblemLanguageResultExecution timeMemory
1200476spampotsKnapsack (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 j = 0; (j*w[i] <= s && j <= k[i]); ++j){ for(int l = s - j*w[i]; l >= 0; l--){ dp[l+j*w[i]] = max(dp[l+j*w[i]], dp[l]+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...