Submission #646253

#	Time	Username	Problem	Language	Result	Execution time	Memory
646253		Tenis0206	Split the sequence (APIO14_sequence)	C++11	0 / 100	42 ms	84448 KiB

sequence

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = INT_MAX;

int n,k;
int v[100005];

int sp[100005];

int dp[100005][2];
signed l[100005][205];

int d[100005];

int sum(int st, int dr)
{
    if(st > dr)
    {
        return 0;
    }
    return sp[dr] - sp[st - 1];
}

long double time_bigger(int a, int b, int j)
{
    pair<int,int> line_a = {sp[a],dp[a][j % 2]};
    pair<int,int> line_b = {sp[b],dp[b][j % 2]};
    return 1.0 * (line_b.second - line_a.second) / (line_a.first - line_b.first);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    ++k;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    for(int i=1; i<=n; i++)
    {
        dp[i][1] = sum(1,i) * sum(i + 1, n);
    }
    for(int j=2; j<=k; j++)
    {
        int p = 1, u = 0;
        d[++u] = 0;
        for(int i=1;i<=n;i++)
        {
            while(p<u && time_bigger(d[p+1],d[p],j-1) <= -1.0 * (sp[n] - sp[i]))
            {
                ++p;
            }
            int poz = d[p];
            dp[i][j % 2] = dp[poz][(j-1) % 2] + sum(poz + 1,i) * sum(i + 1, n);
            l[i][j] = poz;
            while(p<u && time_bigger(i,d[u],j-1) < time_bigger(d[u],d[u-1],j-1))
            {
                --u;
            }
            d[++u] = i;
        }
    }
    cout<<dp[n][k % 2]<<'\n';
    int poz = n;
    vector<int> rez;
    while(poz)
    {
        poz = l[poz][k--];
        if(poz)
        {
            rez.push_back(poz);
        }
    }
    reverse(rez.begin(),rez.end());
    for(auto it : rez)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
    return 0;
}

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