USACO 3.2 Feed Ratios

Could be solved using Gauss Elimination, but there is a constraint on the mixture upper bound (less than 100), so a brutal force search could do it.

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

vector<int> goal(3, 0);
vector<vector<int>> source(3, vector<int>(3, 0));
vector<int> anws(4, 0);
int total = INT_MAX;

bool judge(vector<int> &sum) {
  if (sum[0] < goal[0] || sum[1] < goal[1] || sum[2] < goal[2]) return false;
  if (sum[0] * goal[1] != sum[1] * goal[0]) return false;
  if (sum[1] * goal[2] != sum[2] * goal[1]) return false;
  return true;
}

void fillSum(vector<int> &sum, int i, int j, int k) {
  for (int idx = 0; idx < 3; ++idx) {
    sum[idx] = source[0][idx] * i + source[1][idx] * j + source[2][idx] * k;
  }
}

int main() {
  ifstream fin("ratios.in");
  ofstream fout("ratios.out");
  
  for (int i = 0; i < 3; ++i) {
    fin >> goal[i];
  }
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      fin >> source[i][j];
    }
  }
  
  auto gSum = std::accumulate(goal.begin(), goal.end(), 0);
  
  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {
      for (int k = 0; k < 100; ++k) {
        vector<int> sum(3, 0);
        fillSum(sum, i, j, k);
        if (!judge(sum)) continue;
        if (i + j + k > total) continue;
        total = i + j + k;
        anws[0] = i; anws[1] = j; anws[2] = k;
        anws[3] = std::accumulate(sum.begin(), sum.end(), 0) / gSum;
        break;
      }
    }
  }
  
  if (anws[3] == INT_MAX || (anws[3] == 0 && gSum != 0)) {
    fout << "NONE" << endl;
  } else {
    for (int i = 0; i < 3; ++i) {
      fout << anws[i] << " ";
    }
    fout << anws[3] << endl;
  }
}