Submission #989397

#	Time	Username	Problem	Language	Result	Execution time	Memory
989397		khanhphucscratch	Split the sequence (APIO14_sequence)	C++14	100 / 100	977 ms	82112 KiB

sequence

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[200010], dp[2][100010];
int32_t tv[203][100010];
int c(int l, int r)
{
    return (a[r] - a[l-1]) * (a[n] - a[r]);
}
void calculate(int p, int l, int r, int tl, int tr)
{
    if(l > r) return;
    int bestval = -1, bestplace = 0, mid = (l+r)/2;
    for(int i = tl; i <= tr; i++) if(i <= mid && i >= p){
        int curval = dp[(p&1)^1][i-1] + c(i, mid);
        if(bestval < curval){
            bestval = curval;
            bestplace = i;
        }
    }
    dp[p&1][mid] = bestval; tv[p][mid] = bestplace;
    calculate(p, l, mid-1, tl, bestplace);
    calculate(p, mid+1, r, bestplace, tr);
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin>>n>>k;
    k++;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) a[i] += a[i-1];
    for(int i = 1; i <= k; i++) calculate(i, i, n, 1, n);
    /*for(int i = 1; i <= k; i++){
        for(int j = 1; j <= n; j++) cout<<dp[i][j]<<" ";
        cout<<endl;
    }*/
    cout<<dp[k&1][n]<<'\n';
    vector<int> ans; int place = n;
    for(int i = k; i > 1; i--){
        place = tv[i][place]-1;
        ans.push_back(place);
    }
    reverse(ans.begin(), ans.end());
    for(int i : ans) cout<<i<<" ";
}

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