素直に dp を考えると，
\(dp_{i,j} := \) \([0,i)\) まで見て，最後の休日が \(j\) 日目 のときの min.
しかし，これは失敗する． なぜなら，生産性は，今決めている日だけでなく，先の日の割り当て次第で 今日の近傍の生産性が変わってしまうから．
対策:
今が平日なら，生産性を 計上するのを保留しておく． 休日が来た日に，前回の休日からの生産性をまとめて計上する． これにより， 過去だけ分かっていれば十分となる．
休日同士の間が \(j\) 日で，間がすべて平日の場合， 生産性は \(\sum_{k \in j} a_{\lfloor k/2 \rfloor}\) となる．
実装:
初日を休日とする．
\(dp_{i,j} := \) \([0,i)\) 日まで見て，連続 \(j\) 日が平日であるときの min
とする．
\(for \ i \in n \) で dp を更新． ただし，\(n\) 日でループするので， ループの最後だけは初日が休日としたことと整合性が合うようにする．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vll s(n+2); rep(j,n+1) s[j+1] = s[j] + a[j/2];
vll dp(n, -INFL);
dp[0] = 0;
rep(i,n){
vll old(n, -INFL);
swap(dp, old);
drep(j,i+1){
if(i != n-1) chmax(dp[j+1], old[j]);
chmax(dp[0], old[j]+s[j]);
}
}
cout << dp[0] << endl;
return 0;
}
