Drink Responsibly

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <iomanip>

using namespace std;
typedef long long LL;

LL inf = 1e15;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    double budget_in, target_in; LL nDrinks;
    cin >> budget_in >> target_in >> nDrinks;
    LL budget = budget_in * 100;
    LL target = target_in * 30;
    
    vector<string> names;
    vector<LL> values, costs;
    for(int i = 0; i < nDrinks; i++){
        string s; cin >> s; // name
        names.push_back(s);
        LL value; cin >> value;
        string fraction; cin >> fraction;
        double cost; cin >> cost;
        LL x = fraction[2] - '0';
        value = (value * 30) / x;
        values.push_back(value);
        costs.push_back(cost*100);
    }
    /*cout << target << " " << budget << endl;
    for(auto x : values) cout << x << " "; cout << endl;
    for(auto x : costs) cout << x << " "; cout << endl;*/
    
    vector<vector<LL> > T(target + 5, vector<LL>(nDrinks + 5, inf));
    vector<vector<LL> > backpointers(target + 5, vector<LL>(nDrinks + 5));

    T[0][0] = 0;
    for(int k = 1; k <= nDrinks; k++){
        for(int value = 0; value <= target; value++){
            LL dontuse = T[value][k-1];
            LL usesame = value - values[k-1] >= 0 ? T[value-values[k-1]][k] + costs[k-1] : inf;
            LL usedifferent = value - values[k-1] >= 0 ? T[value-values[k-1]][k-1] + costs[k-1] : inf;
            LL best = min(dontuse,min(usesame,usedifferent));
            
            if(dontuse == best) backpointers[value][k] = 1;
            if(usedifferent == best) backpointers[value][k] = 2;
            if(usesame == best) backpointers[value][k] = 3;
            
            //if(best != inf) cout << value << " " << k << ": " << best << endl;
            T[value][k] = best;
        }
    }
    if(T[target][nDrinks] > budget){
        cout << "IMPOSSIBLE" << endl;
    } else{
        vector<LL> counts(nDrinks+1);
        int value = target;
        int k = nDrinks;
        while(k != 0){
            if(backpointers[value][k] == 1) k--;
            else if(backpointers[value][k] == 2) {
                value -= values[k-1];
                counts[k-1]++;
                k--;
            } else{
                counts[k-1]++;
                value -= values[k-1];
            }
        }
        for(int i = 0; i < nDrinks; i++){
            if(counts[i] != 0){
                cout << names[i] << " " << counts[i] << "\n";
            }
        }
    }
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED