Submission #1200481

#TimeUsernameProblemLanguageResultExecution timeMemory
1200481spampotsKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1604 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) dp[l] = max(dp[l], dp[l-j*w[i]] + j*v[i]); 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...