Untitled

 avatar
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...