USACO 4.1 Beef McNuggests

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int N;
vector<int> vals;

int main() {
    ifstream fin("nuggets.in");
    ofstream fout("nuggets.out");

    fin >> N;
    if (N == 1) {
        cout << 0 << endl;
        fout << 0 << endl;
    }
    vals = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        fin >> vals[i];
    }
    int n = vals[0];
    for (int i = 1; i < N; ++i) {
        n = gcd(n, vals[i]);
        if (n == 1) {
           break;
        }
    }
    if (n != 1) {
        cout << 0 << endl;
        fout << 0 << endl;
        return 0;
    }

    sort(vals.begin(), vals.end());
    int max = vals[N - 1] * vals[N - 2] * gcd(vals[N - 1], vals[N - 2]);
    vector<bool> dp(max, false);
    dp[0] = true;
    for (int i = 0; i < N; ++i) {
        for (int j = vals[i]; j <= max; ++j) {
            if(dp[j - vals[i]]) {
               dp[j] = true;
            }
        }
    }

    for (int i = max; i > 0; --i) {
        if (!dp[i]) {
            cout << i << endl;
            fout << i << endl;
            return 0;
        }
    }
    return 0;
}