Submission #1196715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196715		Muhammad_Aneeq	Split the sequence (APIO14_sequence)	C++20	71 / 100	620 ms	196608 KiB

sequence

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
vector<pii>hull={};
vector<int>ind;
void pr(pii a)
{
    cout<<a.fi<<' '<<a.se<<endl;
}
bool yes=0;
bool com(pii a,pii b)
{
    // pr(a);
    // pr(b);
    if (a.fi/a.se!=b.fi/b.se)
        return a.fi/a.se < b.fi/b.se;
    a.fi%=a.se;
    b.fi%=b.se;
    return (a.fi*b.se<b.fi*a.se);
}
bool cw(pii a,pii b,pii c)
{
    return com({b.fi-a.fi,a.se-b.se},{c.fi-b.fi,b.se-c.se});
}
void insert(pii x,int in)
{
    while (hull.size()&&hull.back()==x)
    {
        hull.pop_back();
        ind.pop_back();
    }
    while (hull.size()>1&&!cw(hull[hull.size()-2],hull.back(),x))
    {
        hull.pop_back();
        ind.pop_back();
    }
    hull.push_back(x);
    ind.push_back(in);
}
int vl(pii a,int x)
{
    return x*a.se+a.fi;
}
pair<int,int> query(int x)
{
    int ans=vl(hull[0],x);
    int in=ind[0];
    int st=1,en=hull.size()-1;
    while (st<=en)
    {
        int mid=(st+en)/2;
        int ans1=vl(hull[mid-1],x),ans2=vl(hull[mid],x);
        if (ans1>ans2)
        {
            if (ans1>ans)
                in=ind[mid-1];
            ans=max(ans,ans1);
            en=mid-1;
        }
        else
        {
            if (ans2>ans)
                in=ind[mid];
            ans=max(ans,ans2);
            st=mid+1;
        }
    }
    return {ans,in};
}
inline void solve()
{
    int n,k;
    cin>>n>>k;
    int a[n+1]={};
    int p[n+1]={};
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[i]=p[i-1]+a[i];
    }
    int dp1[n+1]={};
    for (int i=1;i<=n;i++)
        dp1[i]=p[i]*(p[n]-p[i]);
    int dp[n+1]={};
    map<int,int>pre[k+1]={};
    for (int i=1;i<=n;i++)
        pre[1][k]=-1;
    for (int l=2;l<=k;l++)
    {
        hull={};
        ind={};
        yes=(l==3);
        insert({dp1[l-1]-p[n]*p[l-1],p[l-1]},l-1);
        for (int i=l;i<=n;i++)
        {
            pii y=query(p[i]);
            pre[l][i]=y.se;
            dp[i]=y.fi+(p[n]-p[i])*p[i];
            insert({dp1[i]-p[n]*p[i],p[i]},i);
        }
        for (int i=1;i<=n;i++)
        {
            dp1[i]=dp[i];
            dp[i]=0;
        }
    }
    int ans=-1;
    int ind=1;
    for (int i=1;i<=n;i++)
    {
        if (dp1[i]>ans)
        {
            ans=dp1[i];
            ind=i;
        }
    }
    vector<int>ans1;
    for (int l=k;l>=1;l--)
    {
        ans1.push_back(ind);
        ind=pre[l][ind];
    }
    reverse(begin(ans1),end(ans1));
    cout<<ans<<endl;
    for (auto i:ans1)
        cout<<i<<' ';
    cout<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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