Submission #65138

#	Time	Username	Problem	Language	Result	Execution time	Memory
65138		Vahan	Split the sequence (APIO14_sequence)	C++17	0 / 100	1529 ms	132096 KiB

sequence

#include<iostream>
#include<deque>
using namespace std;
long long d[100007][201],n,k,a[200000],A[200000];
int i,j,cur;
deque<pair<int,int> > q;
bool bad(pair<int,int> x, pair<int,int> y, pair<int,int> z) {
	long long p1=(y.first-z.first) * (y.second-x.second);
	long long p2=(x.first-y.first) * (z.second-y.second);
	return  p1<=p2;

}
void addline(pair<int,int> x)
{
    int r=q.size()-1;
    if(q.size()>=2 && bad(q[r-1],q[r],x))
    {
        q.pop_back();
        r--;
    }
    q.push_back(x);
}
void setcur(long long x)
{
    int u=q.size()-1;
    if (cur >  u)
        cur = u;
    while (cur<u && q[cur + 1].first * x + q[cur + 1].second >= q[cur].first * x + q[cur].second)
        cur++;
}
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        A[i]=A[i-1]+a[i];;
    }
    for(int j=1;j<=k;j++)
        for(int i=1;i<=j;i++)
            d[i][j]=-999999999;
    for(j=1;j<=k;j++)
    {
        q.clear();
        cur=0;
        for(i=1;i<=n;i++)
        {

            if (i>j)
            {
                setcur(A[i]);
                d[i][j] = (A[i]-A[cur+1])*A[cur+1]+d[cur+1][j-1];
            }
            addline(make_pair(A[i],-A[i]*A[i]+d[i][j-1]));
        }
    }
    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*/

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