Untitled
unknown
c_cpp
3 years ago
1.9 kB
5
Indexable
#include <bits/stdc++.h> #define ff first #define ss second #define ll long long #define ld long double #define pb push_back #define mp make_pair #define vi vector<int> #define vl vector<ll> #define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define endl '\n' #define teto(a, b) ((a+b-1)/(b)) using namespace std; // Extra #define all(x) x.begin(), x.end() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // const int MAX = 300010; const ll MOD = (int)1e9 +7; const int INF = 1e9; const ll LLINF = 0x3f3f3f3f3f3f3f3f; const ld EPS = 1e-8; // colocar suposicoes no PAPEL!! Verificar depois vector<pair<int,int>> knap; int32_t main() { sws; int n, E; cin >> n >> E; for(int i = 0; i < n; i++) { ll e, v, q; cin >> e >> v >> q; // bota v, 2*v, 4*v, 8*v, ...,; todas as potencias de 2 que nao estouram q ll qt = 1, tot = 0; while(q > 0) { if(qt > q) break; if( qt*e > E or tot > E ) { q = 0; break; } knap.pb({qt*e, qt*v}); q -= qt; tot += qt*e; qt *= 2; } // se q nao eh potencia de 2 entao sobra um restinho, so jogar ele ai if(q > 0) { knap.pb({q*e, q*v}); } } // dp iterativa com otimizacao de memoria int m = knap.size(); vector<int> ant(E+1, 0); for(int i = (int)m-1; i >= 0; i--) { vector<int> tab(E+1, 0); for(int energia = E; energia >= 0; energia--) { int res = ant[energia]; if(energia - knap[i].ff >= 0) { res = max(res, knap[i].ss + ant[energia - knap[i].ff]); } tab[energia] = res; } swap(tab, ant); } cout << ant[E]<< endl; return 0; }
Editor is loading...