Submission #162533

#	Time	Username	Problem	Language	Result	Execution time	Memory
162533		combi1k1	Split the sequence (APIO14_sequence)	C++14	100 / 100	1603 ms	85180 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

const int   N   = 1e5 + 1;

typedef pair<ll,ll>     ii;

struct  ConvexHull  {
    int tot, ptr;

    ii  line[N];
    int name[N];

    int bad(ii a,ii b,ii c) {
        return  1.0 * (c.Y - a.Y) / (a.X - c.X) <= 1.0 * (b.Y - a.Y) / (a.X - b.X);
    }
    int add(ll s,ll c,int i){
        while (tot > 1) {
            if (bad(line[tot - 1],line[tot],ii(s,c)))   {
                tot--;
                continue;
            }
            break;
        }
        ++tot;
        line[tot] = ii(s,c);
        name[tot] = i;
    }
    ll  get(int i,int x)    {
        return  line[i].X * x + line[i].Y;
    }
    ii  get(int x)  {
        for(ptr = min(ptr,tot) ; ptr < tot && get(ptr,x) <= get(ptr + 1,x) ; ++ptr);
        return ii(get(ptr,x),name[ptr]);
    }
}   Combi;

int a[N], c[N];
ll  f[N], g[N];

int opt[N][205];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;

    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i],
        a[i] += a[i - 1];

    for(int i = 1 ; i <= n ; ++i)   f[i] = 1ll * a[i] * a[i];
    for(int i = 2 ; i <= k + 1 ; ++i)   {
        Combi.tot = 0;
        Combi.ptr = 0;
        for(int j = i ; j <= n ; ++j)   {
            Combi.add(a[j - 1], -f[j - 1] - 1ll * a[j - 1] * a[j - 1],j - 1);

            int t = Combi.get(2 * a[j]).Y;
            ll  C = Combi.get(2 * a[j]).X;

            g[j] = 1ll * a[j] * a[j] - C;

            opt[j][i] = t;
        }
        for(int j = i ; j <= n ; ++j)
            f[j] = g[j];
    }
    cout << (1ll * a[n] * a[n] - f[n]) / 2 << "\n";

    stack<int>  res;

    for(int i = k ; i ; --i)
        res.push(n = opt[n][i + 1]);

    while (res.size())
        cout << res.top() << " ",
        res.pop();
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In member function 'int ConvexHull::add(long long int, long long int, int)':
sequence.cpp:33:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

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