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; }