https://arc092.contest.atcoder.jp/tasks/arc092_c
こういう問題も冷静になればシンプルに書けるんやなって。
結局、要素番号が偶数のやつから好きにとるか、奇数のやつから好きにとるかをすればいいとわかります。
構成法ですが、
1.数列を後から見て、使うやつまで全て消す。
2.数列を前から見て、使うやつまで全て消す。
3.数列の3番目の要素を見て、使うのだったら2番目に対して操作を行い、そうでなかったら3番目に対して操作を行う。
という順番でやれば簡単だと思います。
すべてマイナスの場合だけ注意しましょう。そのときも一番大きいelementを使うとして、上の構成法でできます。
int N, M = 0; int A[MAX_N]; bool B[MAX_N]; int L, R; int ans[MAX_N]; void add(int v) { ans[M++] = v; } void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; ll es = 0, os = 0; //even sum, odd sum bool ok = false;// is B[i] == true exists? ll mx = -linf; int at = -1; //mxv and where mxv is located for(int i = 0; i < N; i++) { if(A[i] >= 0) { B[i] = true; ok = true; if(i % 2 == 0) es += A[i]; else os += A[i]; } if(mx < A[i]) { mx = A[i]; at = i; } } if(!ok) { es = at % 2 == 0 ? mx : -linf; os = at % 2 == 0 ? -linf : mx; B[at] = true; } if(es >= os) { L = 0; R = (N - 1) % 2 == 0 ? N - 1 : N - 2; } else { L = 1; R = (N - 1) % 2 == 0 ? N - 2 : N - 1; } while(!B[L]) L += 2; while(!B[R]) R -= 2; rep(i, 0, N - 1 - R) add(N - 1 - i); rep(i, 0, L) add(0); for(int l = L; l < R; l += 2) { if(!B[l + 2]) add(2); else add(1); } cout << max(es, os) << "\n"; cout << M << "\n"; rep(i, 0, M) { cout << ans[i] + 1 << "\n"; } }