Submission #95375

#	Time	Username	Problem	Language	Result	Execution time	Memory
95375		tduong0806	Split the sequence (APIO14_sequence)	C++14	100 / 100	1946 ms	87800 KiB

sequence

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#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
const int N=100010;
int n,k,a[N],tr[N][210],top;
ll s[N],f[N],p[N],g[N];
db lef[N];
int st[N];
vector<int> kq;
db giao(int u,int v)
{
    return 1.0*(g[v]-g[u])/(s[v]-s[u]);
}
void add(int i,int j)
{
    if(top>=0&&s[i-1]==s[st[top]]) --top;
    while(top>=1&&lef[top]<=giao(i-1,st[top])) --top;
    st[++top]=i-1;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=-1;
        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]=-p[i]*s[st[o]]+g[st[o]]+p[i]*s[i];
            tr[i][j]=st[o];
        }
        forinc(i,j,n-1) g[i]=f[i];
    }
    int I=0,J=k;
    forinc(i,k,n-1) if(f[i]>=f[I]) I=i;
    cout<<f[I]<<"\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:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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