SRM 691 Div1 Medium Moneymanager

X = 0 であるときは、a/b が大きい方が前に来るようにすればよい。
前半・後半に分ける集合を固定したときも、それぞれの集合内では、a/b が大きい方が前に来るのが最適となっている。
あとは、前半・後半にどう分けるかが問題となるのだが、a/b でソートして、後半部分の b の合計を固定すると DP で計算することができる。
自分の実装では、a/b で降順にソートし、前半・後半部分の後ろから敷き詰めていくような DP で解いた。(4 次元の状態数を持つことになるので MLE に注意する)
計算量は、O(N^4*maxB^2)で、少しだけシビアなので、あまり定数倍が重くなりすぎないようにする。

ll dp[2][30][260][260];

class Moneymanager {
	public:
	int getbest(vector <int> a, vector <int> b, int X) {
		int n = a.size()/2;
		vector<P> v(2*n);
		rep(i, 2*n) v[i] = P(a[i], b[i]);
		auto f = [&](const P &i, const P &j){ return i.fst*j.snd<j.fst*i.snd;};
		sort(all(v), f);
		ll sum = 0;
		mset(dp, -1);
		rep(k, 260) dp[0][0][0][k] = 0;
		rep(i, 2*n){
			int t = i%2;
			mset(dp[!t], -1);
			for(int j = 0; j <= min(i, n); j++){
				for(int k = 0; k < 260; k++){
					for(int l = 0; l <= k; l++){
						if(dp[t][j][l][k]<0) continue;
						chmax(dp[!t][j][l][k], dp[t][j][l][k]+(sum-l+k+v[i].snd)*v[i].fst);
						if(l+v[i].snd<=k) chmax(dp[!t][j+1][l+v[i].snd][k], dp[t][j][l][k]+(l+v[i].snd)*(v[i].fst));
					}
				}
			}
			sum += v[i].snd;
		}
		ll res = -INF;
		rep(i, 300){
			if(dp[0][n][i][i]>=0) chmax(res, dp[0][n][i][i]+X*i);
		}
		return res;
	}
};