Submission #75285

#	Time	Username	Problem	Language	Result	Execution time	Memory
75285		zubec	Split the sequence (APIO14_sequence)	C++14	100 / 100	1882 ms	93060 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
 
ll n, m, a[100100], pref[100100];
 
int pr[100100][210];
 
struct line{
    ll k, b;
    int pos;
    inline ll eval(ll x){
        return k*x+b;
    }
};
 
inline ll intersect(line l1, line l2){
    return (l1.b-l2.b)/(l2.k-l1.k);
}
 
inline bool to_erase(line l1, line l2, line l3){
    ll x = intersect(l1, l3);
    return l2.eval(x) <= l3.eval(x);
}
 
int sz1, sz2;
 
line vec[100100], vecCur[100100];
 
inline void insrt(line ln){
    if (sz1 && vec[sz1-1].k == ln.k){
        if (vec[sz1-1].b < ln.b)
            sz1--; else
            return;
    }
    while(sz1 > 2 && to_erase(vec[sz1-2], vec[sz1-1], ln))
        sz1--;
    vec[sz1] = ln;
    ++sz1;
}
 
void swp(){
    swap(vec, vecCur);
    swap(sz1, sz2);
    sz1 = 0;
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    for (int i = 1; i <= n; i++)
        insrt({pref[i], -(pref[i]*pref[i]), i});
    swp();
    ll ans = 0;
    for (int ii = 1; ii <= m; ii++){
        int pos = 0;
        for (int i = ii+1; i <= n; i++){
            while(pos+1 < sz2 && vecCur[pos+1].pos < i && vecCur[pos].eval(pref[i]) <= vecCur[pos+1].eval(pref[i]))
                ++pos;
            pr[i][ii] = vecCur[pos].pos;
            ans = vecCur[pos].eval(pref[i]);
            insrt({pref[i], ans-(pref[i]*pref[i]), i});
        }
        swp();
    }
    cout << ans << endl;
    vector <int> vecAns;
    int x = n, y = m;
    while(x != 0){
        x = pr[x][y];
        y--;
        vecAns.push_back(x);
    }
    vecAns.pop_back();
    for (int i = vecAns.size()-1; i >= 0; i--)
        cout << vecAns[i] << ' ';
 
}
 
/**
 
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