Submission #216807

#	Time	Username	Problem	Language	Result	Execution time	Memory
216807		Autoratch	Split the sequence (APIO14_sequence)	C++14	49 / 100	590 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;
const int K = 201;

int n,k;
int a[N];
long long s[N],dp[2][N],op[K][N];
vector<int> ans;

void compute(int l,int r,int optl,int optr,int f,int id)
{
    if(l>r) return;
    int mid = (l+r)/2;
    long long val = 0;
    int opt;
    for(int k = optl;k <= min(mid,optr);k++)
    {
        long long now = dp[f^1][k]+(s[mid]-s[k])*(s[k]);
        if(now>val) val = now,opt = k;
    }
    op[id][mid] = opt,dp[f][mid] = val;
    compute(l,mid-1,optl,opt,f,id);
    compute(mid+1,r,opt,optr,f,id);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> a[i],s[i] = s[i-1]+a[i];
    for(int i = 1;i <= k;i++) compute(1,n,1,n,i%2,i);
    cout << dp[k%2][n] << '\n';
    for(int i = k,x = n;i >= 1;i--) x = op[i][x],ans.push_back(x);
    reverse(ans.begin(),ans.end());
    for(int x : ans) cout << x << ' ';
}

Compilation message (stderr)

sequence.cpp: In function 'void compute(int, int, int, int, int, int)':
sequence.cpp:23:22: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
     op[id][mid] = opt,dp[f][mid] = val;
     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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