Submission #1124698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124698		Marko2604	Split the sequence (APIO14_sequence)	C++20	22 / 100	17 ms	15688 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100007
using namespace std;
struct line
{
    bool active=false;
    ll k, n;
    ll pos;
    ll eval(ll x)
    {
        return k*x+n;
    }
};
ll sz;
vector<ll>x;
line seg[4*MAXN+7];
void makeSeg(int n1)
{   
    sz=(1<<((int)ceil(log2(n1))));
    while(x.size()<sz) x.push_back(0);
    sort(x.begin(),x.end());
    for(int i=1;i<2*sz;i++) seg[i].active=false;
}
void addLine(line l1, int node, int l, int r)
{
    int mid=(l+r)/2;
    if(!seg[node].active)
    {
        seg[node]=l1;
        return;
    }
    ll elnew = l1.eval(x[l]), ernew=l1.eval(x[r]);
    ll elold = seg[node].eval(x[l]), erold=seg[node].eval(x[r]);
    if(elnew<=elold && ernew<=erold) return;
    else if(elnew>=elold && ernew>=erold)
    {
        seg[node]=l1;
        return;
    }
    if(elnew<=elold) swap(seg[node],l1);
    if(l1.eval(x[mid])>=seg[node].eval(x[mid]))
    {
        addLine(seg[node],2*node+1,mid+1,r);
        seg[node]=l1; 
    }
    else
    {
        addLine(l1,2*node,l,mid);
    }
}
pair<ll,int>getAns(ll xx, int node, int l, int r)
{
    if(!seg[node].active) return make_pair(-1000000000000000,-1);
    if(l==r) return make_pair(seg[node].eval(xx), seg[node].pos);
    pair<ll, int> ans=make_pair(seg[node].eval(xx), seg[node].pos);
    int mid=(l+r)/2;
    if(xx<=x[mid]) ans=max(ans,getAns(xx,2*node,l,mid));
    else ans=max(ans,getAns(xx,2*node+1,mid+1,r));
    return ans;
}
ll a[MAXN];
ll dp[203][MAXN]={};
ll back[203][MAXN]={};
ll pref[MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    pref[0]=0;
    for(int i=1;i<=n;i++) pref[i]=a[i]+pref[i-1];
    for(int i=1;i<=n;i++) x.push_back(pref[i]);
    makeSeg(n);
    for(int j=2;j<=n;j++)
    {
        line l;
        l.active=true;
        l.pos=j-1;
        l.n=dp[0][j-1]-pref[j-1]*pref[j-1];
        l.k=pref[j-1];
        addLine(l,1,0,sz-1);
        back[1][j]=getAns(pref[j],1,0,sz-1).second;
        dp[1][j]=getAns(pref[j],1,0,sz-1).first;
    }
    for(int i=1;i<=n;i++) dp[0][i]=-1000000000000000;
    for(int i=2;i<=k;i++)
    {
        makeSeg(n);
        for(int j=2;j<=n;j++)
        {
            line l;
            l.active=true;
            l.pos=j-1;
            l.n=dp[i-1][j-1]-pref[j-1]*pref[j-1];
            l.k=pref[j-1];
            addLine(l,1,0,sz-1);
            back[i][j]=getAns(pref[j],1,0,sz-1).second;
            dp[i][j]=getAns(pref[j],1,0,sz-1).first;
        }
    }
    cout<<dp[k][n]<<endl;
    vector<int>t;
    while(k>0)
    {
        t.push_back(back[k][n]);
        n=back[k][n];
        k--;
    }
    while(!t.empty())
    {
        cout<<t.back()<<" ";
        t.pop_back();
    }
}

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