Analysis: Mooomoo by Brian Dean

This problem can be solved by dynamic programming. We loop over the fields in sequence; for each field, we subtract out the contribution due to the preceding field, and then we solve essentially a knapsack problem to compute the minimum number of cows that can generate the remaining mooing volume. For the knapsack problem formulation, let M(v) be the minimum number of cows that can generate mooing volume v. We can compute M(v) by taking M(v) = 1 + min(M(v - v(j))) over all cows breeds j, where v(j) is the volume generated by breed j. It takes O(B) time to compute each M(v), and there are at most roughly 100,000 values of v for which we need to run this calculation over all the fields, since the mooing volumes sum to at most 100,000.

Code by Tomek Czajka is below:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int INF = 1000000000;
template<class T> inline int size(const T&c) { return c.size(); }

ifstream fin("mooomoo.in");
ofstream fout("mooomoo.out");

struct Impossible {};

vector<int> breeds;
vector<int> volumes;

void ReadInput() {
  int n,b; fin >> n >> b;
  for(int i=0;i<b;++i) {
    int v; fin >> v; breeds.push_back(v);
  }
  for(int i=0;i<n;++i) {
    int v; fin >> v; volumes.push_back(v);
  }
}

vector<int> knapsack;

void ExtendKnapsack() {
  int t = size(knapsack);
  int v = INF;
  for(int i=0;i<size(breeds);++i) {
    int t2 = t - breeds[i];
    if(t2>=0) v = min(v, 1 + knapsack[t2]);
  }
  knapsack.push_back(v);
}

int Knapsack(int total) {
  if(total<0) throw Impossible();
  while(total >= size(knapsack)) ExtendKnapsack();
  if(knapsack[total]==INF) throw Impossible();
  return knapsack[total];
}

int Solve() {
  knapsack.assign(1, 0);
  int carry = 0;
  int res = 0;
  for(int i=0;i<size(volumes);++i) {
    carry = max(carry-1, 0);
    int v = volumes[i] - carry;
    res += Knapsack(v);
    carry = volumes[i];
  }
  return res;
}

int main() {
  ReadInput();
  try {
    fout << Solve() << "\n";
  } catch (Impossible) {
    fout << "-1\n";
  }
}