Submission #1110677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110677		simona1230	Split the sequence (APIO14_sequence)	C++17	28 / 100	1413 ms	38528 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const long long maxn=1024;

long long n,k;
long long a[200001];

long long dp[maxn][maxn];
long long p[maxn];

void read()
{
    cin>>n>>k;
    for(long long i=1; i<=n; i++)
    {
        cin>>a[i];
        p[i]=p[i-1]+a[i];
    }
}

long long idx[maxn][maxn];
vector<long long> ans;

void rec(long long i,long long c)
{
    if(c==0)return;
    ans.push_back(idx[i][c]);
    rec(idx[i][c],c-1);
}

struct line
{
    long long a,b,id;//a*x + b;
    line(){}
    line(long long _a,long long _b,long long _id)
    {
        a=_a;
        b=_b;
        id=_id;
    }

    long long v(long long x)
    {
        return a*x+b;
    }
};

deque<line> d1,d2;

double pt(line l1,line l2)
{
    return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
}

void push_line(line l,deque<line>&d)
{
    while(d.size()>1&&pt(l,d[d.size()-1])<=pt(l,d[d.size()-2]))d.pop_back();
    d.push_back(l);
}

pair<long long,long long> query(long long x,int idq,deque<line> d)
{
    if(d.size()==0)return {0,0};
    if(d.size()==1)return {d[0].v(x),d[0].id};

long long ans=-1,id=0;
    for(int i=0;i<d.size();i++)
        {
            if(d[i].id>=idq)break;
            ans=max(ans,d[i].v(x));
            if(ans==d[i].v(x))
            {
                id=d[i].id;
            }
        }
        return {ans,id};


    long long l=0,r=d.size()-2;
    while(l<=r)
    {
        long long m=(l+r)/2;
        //cout<<l<<" "<<r<<" . "<<d[m].id<<" "<<d[m+1].id<<" "<<idq<<endl;

        if(d[m].id>=idq)
        {
            r=m-1;
            continue;
        }

        if(d[m].v(x)>d[m+1].v(x)||d[m+1].id>=idq)
        {
            ans=max(ans,d[m].v(x));
            if(ans==d[m].v(x))id=d[m].id;
            r=m-1;
        }
        else
        {
            //cout<<"in"<<endl;
            ans=max(ans,d[m+1].v(x));
            if(ans==d[m+1].v(x))id=d[m+1].id;
            l=m+1;
        }
    }
    return {ans,id};
}
int dp1[101][101];

void solve()
{
    for(int i=0;i<=n;i++)
        push_line({p[i],-p[i]*p[i],i},d1);
    for(long long j=1; j<=k; j++)
    {
        //cout<<"! "<<j<<endl;
        for(long long i=1; i<=n; i++)
        {
            pair<long long,long long> in=query(p[i],i,d1);
            //cout<<i<<" "<<in.first<<" "<<in.second<<endl;
            dp[i][j]=in.first;
            idx[i][j]=in.second;
            push_line({p[i],dp[i][j]-p[i]*p[i],i},d2);
            /*for(long long l=0; l<i; l++)
            {
                long long curr=dp1[l][j-1]+(p[i]-p[l])*p[l];
                if(dp1[i][j]<=curr)
                {
                    dp1[i][j]=curr;
                    idx[i][j]=l;
                }
            }*/
            //cout<<i<<" "<<dp1[i][j]<<endl;
        }
        swap(d1,d2);
        d2.clear();
    }
    cout<<dp[n][k]<<endl;
    rec(n,k);
    sort(ans.begin(),ans.end());
    for(long long i=0; i<k; i++)
        cout<<ans[i]<<" ";
    cout<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    solve();
    return 0;
}
/*
7 3
4 1 3 4 0 2 3

10 1
1 1 0 0 0 0 0 0 0 0
*/

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> query(long long int, int, std::deque<line>)':
sequence.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<d.size();i++)
      |                 ~^~~~~~~~~

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