UVa 11341

based on classic 0-1 knapsack problem, the DAG is extended to 3-dimension, it needs an iteration on the giving out 2-dimension table. When doing, make sure that current table element is above 5. Also, DP matrix need to be initialized to -1 for reaching check...

/* UVas */
/*****************************************************************************/
#define N 11
#define M 101
int t, n, m;
int g[N][M];
int d[N][M];
int main(void) {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                scanf("%d", &g[i][j]);
        memset(d, -1, sizeof(d));
        d[0][0]=0;
        for (int i=1; i<=n; i++)
            for (int j=m; j&&g[i][j]>=5; j--)
                for (int k=m; k>=j; k--)
                    if (d[i-1][k-j]!=-1)
                        d[i][k]=max(d[i][k], d[i-1][k-j]+g[i][j]);
        if (d[n][m]==-1)
            printf("Peter, you shouldn't have played billiard that much.\n");
        else
            printf("Maximal possible average mark - %.2lf.\n", (double)(d[n][m]+1e-9)/n);
    }
}
/*****************************************************************************/