Submission #864783

#	Time	Username	Problem	Language	Result	Execution time	Memory
864783		hqminhuwu	Split the sequence (APIO14_sequence)	C++14	100 / 100	687 ms	97800 KiB

sequence

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

struct line {
    ll k, m, id;
    ll eval (ll x) {return x * k + m;}
    ll its (line u) { 
        if (u.k == k)
            return oo;
        return (m - u.m) / (u.k - k); 
    }
};

bool check (line a, line b, line c){
    return (a.m - b.m) * (c.k - a.k) <= (a.m - c.m) * (b.k - a.k);
}
int n,i,j,s;
ll a[N],ans;
deque <line> q[203];
int trace[N][203];
vector <int> res;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // #ifndef ONLINE_JUDGE
    //    freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    cin >> n >> s;
    forr (i,1,n)
        cin >> a[i], a[i] += a[i - 1];
    forr (i,0,201)
        q[i].pb({0,0,0});
    s++;
    forr (i,1,n){
        ford (j,s,1){
            while (q[j].size() >= 2 && q[j].back().eval(a[i]) <= q[j][q[j].size() - 2].eval(a[i]))
                q[j].pop_back();
            ll f = q[j].back().eval(a[i]);
            ans = max (ans,f);
            //cout << f << " " << q[j].back().id << "  ";
            trace[i][j] = q[j].back().id;
            line cur = {a[i],-a[i] * a[i] + f,i};
            while (q[j + 1].size() >= 2 && check (cur,q[j + 1][0],q[j + 1][1]))
                q[j + 1].pop_front();
            q[j + 1].push_front(cur);
        }
    //    cout << "\n";
    }
    cout << ans << '\n';
    int i = n, j = s;
    while (trace[i][j] != 0){
        res.pb(trace[i][j]);
        i = trace[i][j];
        j--;
    }
    reverse(all(res));
    for (int w : res)
        cout << w << " ";
    return 0;
}
/*

7 3
4 1 3 4 0 2 3

*/

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