Submission #1211644

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

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#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;
int n,k;
ll sq(ll a)
{
    return a*a;
}
void add(ll a,ll b,ll ex,ll p,ll i)
{
    ll c = l[p][0],d = l[p][1],e = l[p][2],lp = l[p][3],rp = l[p][4],ci = l[p][7];
    if(a * (lp+rp)/2 + b < c * (lp+rp)/2 + d)
    {
        l[p][0] = a;
        l[p][1] = b;
        l[p][2] = ex;
        l[p][7] = i;
        i = ci;
        a = c;
        b = d;
        ex  = e;
    }
    if(a * lp + b < l[p][0] * lp + l[p][1])
    {
        if(lp <= (lp+rp)/2 -1)
        {
            if(l[p][5] != -1)
            {
                add(a,b,ex,l[p][5],i);
            }
            else
            {
                l[p][5] = l.size();
                l.pb({a,b,ex,lp,(lp+rp)/2-1,-1,-1,i});
            }
        }
    }
    else
    {
        if(rp >= (lp+rp)/2 + 1)
        {
            if(l[p][6] != -1)
            {
                add(a,b,ex,l[p][6],i);
            }
            else
            {
                l[p][6] = l.size();
                l.pb({a,b,ex,(lp+rp)/2+1,rp,-1,-1,i});
            }
        }
    }
}
vector<ll> check(ll v,int p)
{
    vector<ll> ans;
    ans = {l[p][0] * v + l[p][1],l[p][2],l[p][7]};
    if((l[p][3]+l[p][4])/2 < v && l[p][6] != -1)
    {
        vector<ll> c = check(v,l[p][6]);
        if(c[0] < ans[0])
        {
            ans = c;
        }
    }
    else if((l[p][3]+l[p][4])/2 > v && l[p][5] != -1)
    {
        vector<ll> c = check(v,l[p][5]);
        if(c[0] < ans[0])
        {
            ans = c;
        }
    }
    return ans;
}
ll pref[100000];
vector<int> ord;
pair<ll,ll> solve(ll c)
{
    l.clear();
    ord.clear();
    l.pb({0,0,0,0,inf,-1,-1,-1});
    vector<vector<ll>> ans(n);
    rep(i,n)
    {
        ans[i] = {check(pref[i],0)[0] + pref[i]*pref[i] + c, check(pref[i],0)[1]+1,check(pref[i],0)[2]};
        add(-2 * pref[i],ans[i][0] + pref[i]*pref[i],ans[i][1],0,i);
        
    }
    int i = n-1;
    while(i != -1)
    {
        ord.pb(i);
        i = ans[i][2];
    }
    return {ans[n-1][0] - c*ans[n-1][1],ans[n-1][1]-1};
}
int 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 l = 0;
    ll r = 1e18;
    pair<ll,ll> ans;
    bool lc;
    while(l+1 < r)
    {
        ll mid = (l+r)/2;
        pair<ll,ll> c = solve(mid);
        ans = c;
        if(c.nd < k)
        {
            r = mid;
            lc = 1;
        }
        else if(c.nd > k)
        {
            l = mid;
            lc = 0;
        }
        else
        {
            break;
        }
    }
    ll cm;
    if(lc)
    {
        cm = r;
    }
    else
    {
        cm = l;
    }
    ll tans = ans.st + (k-ans.nd)*cm;
    cout<<(pref[n-1]*pref[n-1]- tans)/2<<"\n";
    set<int> o;
    o.insert(-1);
    rep(i,ord.size())
    {
        o.insert(ord[i]);
    }
    if(k > ans.nd)
    {
        rep(j,5)
        {
            rep(i,n)
            {
                if(!o.contains(i))
                {
                    auto q = o.upper_bound(i);
                    int b = *q;
                    q--;
                    int a = *q;
                    if((a != -1 && sq(pref[b] - pref[a]) - sq(pref[b] - pref[i]) - sq(pref[i] - pref[a]) == cm) || (a == -1 && sq(pref[b]) - sq(pref[b] - pref[i]) - sq(pref[i]) == cm))
                    {
                        o.insert(i);
                        ans.nd++;
                        if(k == ans.nd)
                        {
                            break;
                        }
                    }
                }
            }
        }
    }
    else if(ans.nd > k)
    {
        rep(j,5)
        {
            rep(i,n-1)
            {
                if(o.contains(i))
                {
                    auto q = o.upper_bound(i);
                    int b = *q;
                    q--;q--;
                    int a = *q;
                    if((a != -1 && sq(pref[b] - pref[a]) - sq(pref[b] - pref[i]) -sq(pref[i] - pref[a]) == cm) || (a == -1 && sq(pref[b]) - sq(pref[b] - pref[i]) - sq(pref[i]) == cm))
                    {
                        o.erase(i);
                        ans.nd--;
                        if(k == ans.nd)
                        {
                            break;
                        }
                    }
                }
            }
        }
    }
    for(int i : o)
    {
        if(i != -1 && i != n-1)
        {
            cout<<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