Submission #1171530

#TimeUsernameProblemLanguageResultExecution timeMemory
1171530SG2AlokKnapsack (NOI18_knapsack)C++20
73 / 100
275 ms327680 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; typedef long long ll; using namespace __gnu_pbds; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(0); #define fi first #define se second template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>; const ll MOD1 = 1e9 + 7; const ll MOD = 998244353; const ll INF = 4500000000000000000LL; const ll mod1 = 6900000469; const ll mod2 = 698000002369; const int block = 447; ll n, m, k, q, a[1200005], b[500005], c[500005]; string s, s1, s2; int main(){ hitaf int T = 1; // cin >> T; while(T--){ cin >> m >> n; for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i]; vector<vector<ll>> dp(n + 2, vector<ll>(m + 2, -INF)); dp[0][0] = 0; for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ dp[i][j] = dp[i - 1][j]; for(int k = b[i], val = a[i]; k <= j && k <= c[i] * b[i]; k += b[i], val += a[i]){ dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + val); } } } ll maks = 0; for(int j = 0; j <= m; j++) maks = max(maks, dp[n][j]); cout << maks << endl; } }
#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...