Submission #1124712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124712		Marko2604	Split the sequence (APIO14_sequence)	C++20	71 / 100	595 ms	162428 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100007
using namespace std;
struct line
{
    ll k, n;
    ll pos;
    ll eval(ll x)
    {
        return k*x+n;
    }
};
ll a[MAXN];
ll dp[2][MAXN]={};
ll back[205][MAXN]={};
ll pref[MAXN];
vector<line>st;
int pk;
double inter(line l1, line l2)
{
    if(l1.k==l2.k) return 1000000000;
    return (double)(l2.n-l1.n)/(l1.k-l2.k);
}
void addLine(line l)
{
    while(st.size()>=2 && inter(st.back(),l)<inter(st.back(),st[st.size()-2])) st.pop_back();
    st.push_back(l);
}
pair<ll,int> getAns(ll x)
{
    pk=min(pk,(int)st.size()-1);
    pk=max(0,pk);
    while(pk<st.size()-1 && st[pk].eval(x)<=st[pk+1].eval(x)) pk++;
    while(pk>0 && st[pk].eval(x)<st[pk-1].eval(x)) pk--;
    return make_pair(st[pk].eval(x), st[pk].pos);
}
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<=k;i++)
    {
        st.clear();
        pk=0;
        for(int j=2;j<=n;j++)
        {
            line l;
            l.pos=j-1;
            l.n=dp[(i+1)%2][j-1]-pref[j-1]*pref[j-1];
            l.k=pref[j-1];
            addLine(l);
            back[i][j]=getAns(pref[j]).second;
            dp[i%2][j]=getAns(pref[j]).first;
        }
    }
    cout<<dp[k%2][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: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29