Submission #63050

#	Time	Username	Problem	Language	Result	Execution time	Memory
63050		Vahan	Split the sequence (APIO14_sequence)	C++17	11 / 100	2054 ms	34056 KiB

sequence

#include<iostream>
#include<deque>
using namespace std;
long long d[100007][201],n,k,a[200000],A[200000];
int i,j;
deque<int> q;
int m(int x,int y)
{
    if(x==y)
        return -1;
    return (A[i]-A[y])*A[y]+d[y][j-1]-(A[i]-A[x])*A[x]-d[x][j-1];
}
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        A[i]=A[i-1]+a[i];;
    }
    for(j=1;j<=k;j++)
    {
        q.clear();
        for(i=j;i<=n;i++)
        {
            for(int u=1;u<q.size();u++)
            {
                if(m(q[0],q[u])>=0)
                {
                    q.pop_front();
                    u-=2;
                }
            }
            if (!q.empty())
                d[i][j] = (A[i]-A[q[0]])*A[q[0]]+d[q[0]][j-1];
            /*while (q.size() >= 2 && m(q[q.size()-2], q[q.size()-1])< m(q[q.size()-1],i))
                q.pop_back();*/
            q.push_back(i);
        }
    }
    cout<<d[n][k]<<endl;
    int l=n,r=k;
    for(i=n-1;i>=1;i--)
    {
        if((A[l]-A[i])*A[i]+d[i][r-1]==d[l][r])
        {
            cout<<i<<" ";
            r--;
            if(r==0)
                break;
            l=i;
        }
    }
    return 0;
}
/*
7 3
4 1 3 4 0 2 3*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int u=1;u<q.size();u++)
                         ~^~~~~~~~~

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