Submission #95370

#	Time	Username	Problem	Language	Result	Execution time	Memory
95370		tduong0806	Split the sequence (APIO14_sequence)	C++14	60 / 100	129 ms	132096 KiB

sequence

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define int long long
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define pb push_back
#define db double
#define pii pair<int,int>
#define fi first
#define se second
#define piii pair<int,pii>
#define sf se.fi
#define ss se.se
const int N=100010;
int f[N][210],n,k,a[N],s[N],p[N],tr[N][210],top;
db lef[N];
piii st[N];
vector<int> kq;
db giao(piii u,piii v)
{
    return 1.0*(v.ss-u.ss)/(u.sf-v.sf);
}
void add(int i,int j)
{
    if(i==1&&j!=1) return;
    piii O={i-1,{-s[i-1],f[i-1][j-1]}};
    if(top>=0&&O.sf==st[top].sf) --top;
    while(top>=1&&lef[top]<=giao(O,st[top])) --top;
    st[++top]=O;lef[top]=giao(st[top],st[top-1]);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("sequence.inp","r",stdin);
    cin>>n>>k;
    forinc(i,1,n) cin>>a[i],s[i]=s[i-1]+a[i];
    forinc(i,1,n) p[i]=s[n]-s[i];
    forinc(j,1,k)
    {
        top=0;
        forinc(i,j,n-1)
        {
            add(i,j);
            int l=1,r=top,o=0;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(lef[mid]>p[i]) o=mid,l=mid+1;
                else r=mid-1;
            }
            f[i][j]=p[i]*st[o].sf+st[o].ss+p[i]*s[i];
            tr[i][j]=st[o].fi;
        }
    }
    int I=0,J=k;
    forinc(i,k,n-1) if(f[i][k]>=f[I][k]) I=i;
    cout<<f[I][J]<<"\n";
    while(J)
    {
        kq.pb(I);
        I=tr[I][J],J--;
    }
    reverse(kq.begin(),kq.end());
    forv(x,kq) cout<<x<<" ";
}

Compilation message (stderr)

sequence.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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