Submission #1214417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214417		Szymon_Pilipczuk	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	324 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<ll>> l[201];
int n,k;
ll sq(ll a)
{
    return a*a;
}
void add(ll a,ll b,ll p,ll i,int c)
{
    ll d = l[c][p][0],e = l[c][p][1],lp = l[c][p][2],rp = l[c][p][3],ci = l[c][p][6];
    if(a * (lp+rp)/2 + b < d * (lp+rp)/2 + e) 
    {
        l[c][p][0] = a;
        l[c][p][1] = b;
        l[c][p][6] = i;
        i = ci;
        a = d;
        b = e;
    }
    //cerr<<a<<" "<<b<<" "<<p<<" "<<i<<" "<<c<<" "<<l[c][p][4]<<" "<<l[c][p][5]<<"\n";
    if(a * lp + b < l[c][p][0] * lp + l[c][p][1])
    {
        if(lp <= (lp+rp)/2 -1)
        {
            if(l[c][p][4] != -1)
            {
                add(a,b,l[c][p][4],i,c);
            }
            else
            {
                l[c][p][4] = l[c].size();
                l[c].pb({a,b,lp,(lp+rp)/2,-1,-1,i});
            }
        }
    }
    else
    {
        if(rp >= (lp+rp)/2 + 1)
        {
            if(l[c][p][5] != -1)
            {
                add(a,b,l[c][p][5],i,c);
            }
            else
            {
                l[c][p][5] = l[c].size();
                l[c].pb({a,b,(lp+rp)/2+1,rp,-1,-1,i});
            }
        }
    }
}
vector<ll> check(ll v,int p,int c)
{
    vector<ll> ans;
    ans = {l[c][p][0] * v + l[c][p][1],l[c][p][6]};
    if((l[c][p][2]+l[c][p][3])/2 < v && l[c][p][5] != -1)
    {
        vector<ll> cans = check(v,l[c][p][5],c);
        if(cans[0] < ans[0])
        {
            ans = cans;
        }
    }
    else if((l[c][p][2]+l[c][p][3])/2 > v && l[c][p][4] != -1)
    {
        vector<ll> cans = check(v,l[c][p][4],c);
        if(cans[0] < ans[0])
        {
            ans = cans;
        }
    }   
    return ans;
}
ll pref[100000];
vector<int> ord;
ll solve()
{
    l[0].pb({0,0,0,inf,-1,-1,-1});
    for(int i = 1;i<=k;i++)
    {
        l[i].pb({0,inf,0,inf,-1,-1,-1});
    }  
    vector<vector<vector<ll>>> ans(n);
    rep(i,n)
    {
        //cout<<i<<"\n";
        ans[i].resize(k+1);
        for(int j = k;j > 0;j--)
        {
            ans[i][j] = {check(pref[i],0,j-1)[0] + pref[i]*pref[i],check(pref[i],0,j-1)[1]};
            //cout<<ans[i][j][0]<<"\n";
            add(-2 * pref[i],ans[i][j][0] + pref[i]*pref[i],0,i,j);
            //cout<<ans[i][j][0]<<" "<<ans[i][j][1]<<" "<<i<<" "<<j<<"\n";
            //cout<<-2*pref[i]<<" "<<ans[i][j][0] +pref[i]*pref[i]<<"\n";
        }
    }
    //cout<<'a'<<"\n";
    int ci = check(pref[n-1],0,k)[1];
    int cu = k;
    while(ci != -1)
    {
        ord.pb(ci);
        ci = ans[ci][cu][1];
        cu--;
    }
    return check(pref[n-1],0,k)[0] + pref[n-1]*pref[n-1];
}
int32_t main()
{
    cin>>n>>k;
    int cu;
    cin>>cu;
    pref[0] = cu;  
    for(int i = 1;i<n;i++)
    {
        int c;
        cin>>c;
        pref[i] = pref[i-1]+c;
    }
    ll ans = solve();
    reverse(all(ord));
    cout<<(sq(pref[n-1])-ans)/2<<"\n";
    rep(i,k)
    {
        cout<<ord[i]+1<<" ";
    }
    cout<<"\n";
}

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