USACO 3.3 Shopping Offers

#include <vector>
#include <cstring>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>

using namespace std;

int dp[6][6][6][6][6];
// 2nd dimension stores the offer price as element 0, (normalized) product
// code as element 1, 2, 3, 4, 5.
vector<vector<int>> offer(106, vector<int>(6, 0));
// Normalize product code to the range of 1-5 inclusive.
unordered_map<int, int> map;
int s;
int totalOffers;
vector<int> buy(vector<int>(6, 0));
int sentinel;

int compute(int a1,int a2, int a3,int a4,int a5){
    if(dp[a1][a2][a3][a4][a5] != sentinel)
        return dp[a1][a2][a3][a4][a5];
    int w1,w2,w3,w4,w5, ret = sentinel;
    for(int i = 1; i <= totalOffers; ++i){
        w1 = a1 - offer[i][1];w2 = a2 - offer[i][2];
        w3 = a3 - offer[i][3];w4 = a4 - offer[i][4];
        w5 = a5 - offer[i][5];
        if(w1 < 0 || w2 < 0 || w3 < 0 || w4 < 0 || w5 < 0) continue;
        if(dp[w1][w2][w3][w4][w5] == sentinel) {
            dp[w1][w2][w3][w4][w5] = compute(w1,w2,w3,w4,w5);
        }
        ret = std::min(ret, dp[w1][w2][w3][w4][w5] + offer[i][0]);
    }
    return ret;
}

int main() {
    ifstream fin("shopping.in");
    ofstream fout("shopping.out");
    fin >> s;
    int n, c, k, b, code = 0;
    for (int i = 1; i <= s; ++i) {
        fin >> n;
        for (int j = 0; j < n; ++j) {
            fin >> c >> k;
            if (map.find(c) == map.end()) {
                map[c] = ++code;
            }
            offer[i][map[c]] = k;
        }
        fin >> offer[i][0];
    }
    
    fin >> b;
    totalOffers = s + b;
    for(int i = 1; i <= b; ++i){
        fin >> c >> k;
        if (map.find(c) == map.end()) {
            map[c] = ++code;
        }
        offer[s + i][map[c]] = 1;
        buy[map[c]] = k;
        fin >> offer[s + i][0];
    }
    
    memset(dp, 0xf, sizeof(dp));
    sentinel = dp[0][0][0][0][0];
    dp[0][0][0][0][0] = 0;
    int ret = compute(buy[1], buy[2], buy[3], buy[4], buy[5]);
    cout << ret << endl;
    fout << ret << endl;
    return 0;
}