Submission #1040186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040186		dpsaveslives	Split the sequence (APIO14_sequence)	C++17	100 / 100	282 ms	83116 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
const int MAXK = 210;
int split[MAXK][MAXN];
ll arr[MAXN], pref[MAXN], dp[2][MAXN], Q[MAXN];
int N;
bool check1(int x, int y, int j){
    return (dp[0][y]-dp[0][x] >= (pref[y]-pref[x])*(pref[N]-pref[j]));
}
bool check2(int x, int y, int j){
    return ((dp[0][y]-dp[0][x])*(pref[j]-pref[y]) <= (dp[0][j]-dp[0][y])*(pref[y]-pref[x]));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int K; cin >> N >> K;
    fill(dp[0],dp[0]+N+1,0);
    for(int i = 1;i<=N;++i){
        cin >> arr[i];
        pref[i] = pref[i-1]+arr[i]; //pref[i] includes arr[i]
    }
    int l = 1, r = 1;
    for(int i = 1;i<=K;++i){
        Q[r] = 0; ++r;
        for(int j = 1;j<=N;++j){
            while(r-l > 1 && check1(Q[l],Q[l+1],j)){
                ++l;
            }
            dp[1][j] = dp[0][Q[l]]+(pref[j]-pref[Q[l]])*(pref[N]-pref[j]);
            split[i][j] = Q[l];
            while(r-l > 1 && check2(Q[r-2],Q[r-1],j)){
                --r;
            }
            Q[r] = j; ++r;
        }
        l = r = 1;
        for(int j = 1;j<=N;++j){
            dp[0][j] = dp[1][j];
        }
    }
    ll ans = -1; int pos = -1;
    for(int i = 1;i<=N;++i){
        if(dp[0][i] > ans){
            ans = dp[0][i];
            pos = i;
        }
    }
    cout << ans << "\n";
    for(int i = 0;i<K;++i){
        cout << pos << " ";
        pos = split[K-i][pos];
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29