数学の試験

タイトルリンク
題意:n個の数のうち2つの長さkの不連続区間を選択し、2つの区間と最大とする.
問題解:sum配列記録接頭辞和、sum 1配列記録はiを末尾とし、区間長kの区間和は、2 k目から遍歴し、maxx 1は0からi-kまでの間で最大の区間和を維持し、i-kからiまでの区間は0からi-kまでの区間とは無関係であるため、maxx 2はこの2つの区間の総和の最大値を維持することができる.
ACコード:

//
//Write by Yuan Xilan on 2019...
//
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
const int maxn = 2e+5+5;
const ll INF = -1e+18;
ll a[maxn],sum[maxn],sum1[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n,k;
        cin >> n >> k;
        for(int i=1; i<=n; ++i) cin >> a[i];
        sum[0] = 0;
        for(int i=1; i<=n; ++i) sum[i] = sum[i-1] + a[i];
        for(int i=k; i<=n; ++i) sum1[i] = sum[i] - sum[i-k];
        ll maxx1 = INF;ll maxx2 = INF;
        for(int i=k*2; i<=n; ++i){
            maxx1 = max(maxx1,sum1[i-k]);
            maxx2 = max(maxx2,maxx1+sum1[i]);
        }
        cout << maxx2 << endl;
    }
    return 0;
}