【題解】Codeforces 1389B. Array Walk

【題目敘述】http://codeforces.com/contest/1389/problem/B

#include <iostream>
using namespace std;
 
int t, n, k, z, a[100005], pre[100005], ans, mx;
 
int main() {
    cin >> t;
    while (t--){
        cin >> n >> k >> z;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            pre[i] = pre[i-1]+a[i];
        }
        a[n+1] = 0;
        int mx = 0, pos, tmp = 0;
        ans = 0;
        mx = 0;
        for (int i = z; i >= 0; i--){
            pos = 1+k-i*2;
            if (pos < 1) continue;
            for (int j = tmp+1; j <= pos; j++){
                mx = max(mx, a[j]+a[j+1]);
            }
            tmp = pos;
            ans = max(ans, pre[pos]+mx*i);
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends