Submission #65142

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

sequence

#include<iostream>
#include<deque>
using namespace std;
long long d[100007][201],n,k,a[200000],A[200000];
long long i,j,cur;
deque<pair<long long,long long> > q;
bool bad(pair<long long,long long> x, pair<long long,long long> y, pair<long long,long long> 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<long long,long long> x)
{
    long long 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)
{
    long long 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(j=1;j<=k;j++)
    {
        q.clear();
        cur=0;
        for(i=1;i<=n;i++)
        {

            if (i>j)
            {
                setcur(A[i]);
                d[i][j] = q[cur].first*A[i]+q[cur].second;
            }
            if(i>j-1)
                addline(make_pair(A[i],-A[i]*A[i]+d[i][j-1]));
        }
    }
    cout<<d[n][k]<<endl;
    long long 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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29