Submission #1223219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223219		Szymon_Pilipczuk	수열 (APIO14_sequence)	C++20	33 / 100	6 ms	3144 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;
int n,k;
ll sq(ll a)
{
    return a*a;
}
int l = 0,r = 0;
ll dq[100000][5];
ll pref[100000];
vector<int> ord;
int p[200][99999];
ll c[99999][2];
bool add(ll a,ll b,int i)
{
    if(r < l)
    {
        r++;
        dq[r][0] = 0;
        dq[r][1] = infl;
        dq[r][2] = a;
        dq[r][3] = b;
        dq[r][4] = i;
        return 0;
    }
    vector<ll> c = {dq[r][0],dq[r][1],dq[r][2],dq[r][3],dq[r][4]};
    if(c[2] == a)
    {
        if(c[3] > b)
        {
            r--;
            return 1;
        }
    }
    else
    {
        ll cu = (b-c[3])/(c[2]-a) + 1;
        if(cu <= c[0])
        {
            r--;
            return 1;
        }
        else
        {
            dq[r][1] = cu-1;
            r++;
            dq[r][0] = 0;
            dq[r][1] = infl;
            dq[r][2] = a;
            dq[r][3] = b;
            dq[r][4] = i;
        }
    }
    return 0;
}
pair<ll,ll> check(ll c)
{
    while(dq[l][1] < c)
    {
        l++;
    }
    return {c * dq[l][2] + dq[l][3],dq[l][4]};
}

ll solve()
{
    rep(q,k)
    {
        rep(i,n-1)
        {
            c[i][0] = c[i][1];
        }
        l = 0;
        r = -1;
        while(add(0,inf,-1));
        if(q == 0)
        {
            while(add(0,0,-1));
        }
        rep(i,n-1)
        {
            p[q][i] = check(pref[i]).nd;
            c[i][1] = check(pref[i]).st;
            if(q != 0)
            {
                while(add(-2 * pref[i],c[i][0] + sq(pref[i])*2,i));
            }   
        }
    }
    l = 0;
    r = -1;
    rep(i,n-1)
    {   
        while(add(-2 * pref[i],c[i][1] + sq(pref[i])*2,i));
    }
    int ci = check(pref[n-1]).nd;
    int cu = k-1;
    while(ci != -1)
    {
        ord.pb(ci);
        ci = p[cu][ci];
        cu--;
    }
    reverse(all(ord));
    return check(pref[n-1]).st + pref[n-1]*pref[n-1];
}
int32_t main()  
{
    cin>>n>>k;
    int cu;
    cin>>cu;
    pref[0] = cu;  
    rep(i,n-1)
    {
        int c;
        cin>>c;
        pref[i+1] = pref[i]+c;
    }
    ll ans = solve();
    cout<<(sq(pref[n-1])-ans)/2<<"\n";
    rep(i,k)
    {
        cout<<ord[i]+1<<" ";
    }
    cout<<"\n";
}  

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