equeue [AtCoder Beginner Contest 128 D]

https://atcoder.jp/contests/abc128/tasks/abc128_d

解説

https://atcoder.jp/contests/abc128/submissions/5778155

400点であるが、らしからぬように見える。
この辺の点数帯は、難しいアルゴリズムを適用するだけじゃなさそうならば、なるべく簡単に考えることが重要である。
簡単な方針を考えると、何個か選んで取ったあと、何個か選んで入れることで最大化する方針がある。
宝石は左右から順番にしか取れないので、左から何個・右から何個で全探索する。
K回まで余裕があれば、いらないものを戻すことができる。
これは小さい順に戻していけばいい。
これは左右のとり方O(N^2)であるため、十分に間に合う。

int N, K, V[50];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> V[i];

	int ans = 0;
	rep(L, 0, N + 1) rep(R, 0, N + 1) {
		if (N < L + R) continue;
		int rest = K - (L + R);
		if (rest < 0) continue;

		vector<int> has;
		rep(i, 0, L) has.push_back(V[i]);
		rep(i, 0, R) has.push_back(V[N - 1 - i]);
		sort(all(has));

		int n = has.size();
		int sm = 0;
		fore(i, has) sm += i;
		rep(i, 0, min(rest, n)) {
			if (0 < has[i]) break;
			sm -= has[i];
		}
		chmax(ans, sm);
	}
	cout << ans << endl;
}