Submission #59076

#	Time	Username	Problem	Language	Result	Execution time	Memory
59076		zubec	Split the sequence (APIO14_sequence)	C++14	71 / 100	2063 ms	89184 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;
    //set<line>::iterator it;

    line(ll _k, ll _b, int _pos){
        k = _k;
        b = _b;
        pos = _pos;
    }

    ld eval(ll x){
        return k*x+b;
    }

};

inline bool to_erase(line l1, line l2, line l3){
    return ((l3.b-l1.b)/(l1.k-l3.k) > (l3.b-l2.b)/(l2.k-l3.k));
}

vector <line> vec, vecCur;

void insrt(line ln){
    if (!vec.empty() && vec.back().k == ln.k){
        if (vec.back().b < ln.b)
            vec.pop_back(); else
            return;
    }
    while((int)vec.size() > 2 && ((ln.b-vec[vec.size()-2].b)/(vec[vec.size()-2].k-ln.k) > (ln.b-vec.back().b)/(vec.back().k-ln.k)))
        vec.pop_back();
    vec.push_back(ln);
}

void swp(){
    vec.swap(vecCur);
    vec.clear();
}

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(line(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 < (int)vecCur.size() && 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(line(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: 0 / 29