SRM520 Div1 Easy - SRMCodingPhase

問題

今回のSRMは75分で3問あり、i問目はp[i]点満点で、現在の実力では開いてからs[i]分かければ確実に解ける
問題を開いてからt秒後に提出した場合に貰える得点は以下の通り
　1問目: p[0]-2t
　2問目: p[1]-4t
　3問目: p[2]-8t
また最初にluckをlポイント持っていて、これを1ポイント使うたびに、今解いている問題を解き終わるまでの時間が1分縮む
問題選択やluckの配分をうまくやることで最高で何点取れるか

解法

dp

実装

dp[i][j][k]: i問目までで時間をj分、luckをkポイント使った場合の得点の最大値
luckをmポイント使ってi問目を解くと得られる得点は
p[i] - (2^(i+1)) * (s[i]-m)
mの下限は "s[i]-mが残り時間以下である" ような値
mの上限は "k+lがluckの初期値l以下である" かつs[i]未満の値
(問題を解くのに1分は必ずかかるらしいから)

class SRMCodingPhase {
	public:
		int countScore(vector<int> p, vector<int> s, int l) {
			int dp[4][77][111] = {}, res = 0;
			rep(i,3) rep(j,77) rep(k,111) rep(m,s[i]) {
				if (j+s[i]-m<=75 && k+m<=l) chmax(dp[i+1][j+s[i]-m][k+m], dp[i][j][k] + p[i] - (1<<(i+1))*(s[i]-m));
				chmax(dp[i+1][j][k], dp[i][j][k]);
			}
			rep(i,77) rep(j,111) chmax(res, dp[3][i][j]);
			return res;
		}
};