USACO 3.1 Inflation

This is a standard ‘Complete Knapsack’ problem. First stab:

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

using namespace std;

int M /* minutes */, N /* classes */;

int main() {
  ifstream fin("inflate.in");
  ofstream fout("inflate.out");
  fin >> M >> N;
  vector<vector<int>> dp;
  vector<int> w;
  vector<int> v;
 
  dp = vector<vector<int>>(N + 1, vector<int>(M + 1));
  w = vector<int>(N, 0);
  v = vector<int>(N, 0);
  for (int i = 0; i < N; ++i) {
    fin >> v[i] >> w[i];
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= M; ++j) {
      if (j < w[i]) {
        dp[i + 1][j] = dp[i][j];
      } else {
        dp[i + 1][j] = std::max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
      }
    }
  }
  
  fout << dp[N][M] << endl;
  cout << dp[N][M] << endl;
}

This solution exceeds the memory limit (16MB, it seems) set by the problem judge. So the optimization of using a rolling array to compress the states is required. It is possible to do the optimization because the compute of a given state only depends on the value of the current state and the value of previous state.
Now this one passes:

int main() {
  ifstream fin("inflate.in");
  ofstream fout("inflate.out");
  fin >> M >> N;
  vector<int> dp = vector<int>(M + 1);
  vector<int> w = vector<int>(N, 0);
  vector<int> v = vector<int>(N, 0);
  
  for (int i = 0; i < N; ++i) {
    fin >> v[i] >> w[i];
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= M; ++j) {
      dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  
  fout << dp[M] << endl;
  cout << dp[M] << endl;
}