UVa 1231 - ACORN

Accepted date: 2017-07-13
Run Time: 0.260
Ranking (as of 2017-07-13): 114 out of 373
Language: C++

/*
  UVa 1231 - ACORN

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_1231_ACORN.cpp

  This is an accepted solution.
*/

#include <algorithm>
#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int t_max = 2000, h_max = 2000;

int acorns[t_max][h_max + 1];
  // acorns[i][j] is the number of acorns at height j on the i-th tree
int collections[t_max][h_max + 1];
  // collections[i][j] is the max. number of acorns collected at height j on the i-th tree
int max_collections[h_max + 1];
  // max_collections[j] is the max. number of acorns collected at height j

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int c;
  scanf("%d", &c);
  while (c--) {
    int t, h, f;
    scanf("%d %d %d", &t, &h, &f);
    for (int j = 1; j <= h; j++) {
      for (int i = 0; i < t; i++)
        acorns[i][j] = collections[i][j] = 0;
      max_collections[j] = 0;
    }
    for (int i = 0; i < t; i++) {
      int a;
      scanf("%d", &a);
      while (a--) {
        int n;
        scanf("%d", &n);
        acorns[i][n]++;
      }
    }
    for (int j = 1; j <= h; j++)
      for (int i = 0; i < t; i++) {
        collections[i][j] = collections[i][j - 1];
        if (j > f)
          collections[i][j] = max(collections[i][j], max_collections[j - f]);
        collections[i][j] += acorns[i][j];
        max_collections[j] = max(max_collections[j], collections[i][j]);
      }
    printf("%d\n", max_collections[h]);
  }
  scanf("%*d");
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0; // discard "0"
}