Submission #767205

#TimeUsernameProblemLanguageResultExecution timeMemory
767205synthesisKnapsack (NOI18_knapsack)C++17
73 / 100
132 ms262144 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define pii pair<int, int> #define pb push_back #define vi vector<int> #define all(x) x.begin(), x.end() using namespace std; using namespace __gnu_pbds; using ll = long long int; using ull = unsigned long long int; constexpr ll mod = 1e9 + 7; constexpr ll INF = LONG_LONG_MAX; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; string moves = "URDL"; int main() { //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q; /*freopen("problemname.in", "r", stdin); freopen("problemname.out", "w", stdout);*/ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int x, n; cin >> x >> n; int a[n], b[n], c[n]; //value, weight, quantity for(int i = 0;i<n;++i) { cin >> a[i] >> b[i] >> c[i]; } int dp[n + 1][x + 1], ans = 0; memset(dp, 0, sizeof dp); for(int i = 1;i<=n;++i) { for(int j = 0;j<=x;++j) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); int cnt = 1; while(j - cnt*b[i - 1] >= 0 && cnt <= c[i - 1]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - cnt*b[i - 1]] + cnt*a[i - 1]); ++cnt; } ans = max(ans, dp[i][j]); } } cout << ans << endl; 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...