hack101 contest strategy, fleimgruber

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define all(a) (a).begin(),(a).end()
#define pb push_back
#define sz(a) ((int)(a).size())
#define mp make_pair
#define fi first
#define se second

typedef pair<int,int> pint;
typedef long long ll;
typedef vector<int> vi;


#define MAX_N 3005
#define INF 123456789876543LL

int n,d,t[MAX_N];
ll dp[MAX_N][MAX_N];

//persons [0..i-1] know the problems
//persons [0..j-1] is not explaining anymore
ll f(int i, int j)
{
    //everyone knows the problems and nobody is explaining
    //anymore -> solved all the problems
    if (i==n&&j==n)
        return 0;
    //more (or all) people that know the problems
    //don't explaining anymore -> that means there's
    //no way to tell the remaining people about them
    if (j>=i)
        return INF;
    if (dp[i][j]!=-1)
        return dp[i][j];
    ll a=INF;
    //all of the (i-1)-(j-1) = i-j people teach
    //so now 2*i-j people know the problems (and at most all)
    int explaining=min(n,2*i-j);
    if (explaining>i)
        a=d+f(explaining,j);
    //one person stops explaining and solves his problem
    return dp[i][j]=min(a,max(1LL*t[j],f(i,j+1)));
}

int main()
{
    int tc;
    scanf("%d",&tc);
    while (tc--)
    {
        scanf("%d %d",&n,&d);
        for (int i=0; i<n; i++)
            scanf("%d",t+i);
        sort(t,t+n,greater<int>());
        for (int i=0; i<=n; i++)
            for (int j=0; j<=n; j++)
                dp[i][j]=-1;
        printf("%lld\n",f(1,0));
    }
    return 0;
}