Submission #59072

#	Time	Username	Problem	Language	Result	Execution time	Memory
59072		zubec	Split the sequence (APIO14_sequence)	C++14	71 / 100	1572 ms	132096 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

ll n, m, a[100100], pref[100100], dp[100100][210];

struct line{
    ll k, b;
    int pos;
    //set<line>::iterator it;

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

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

};

inline ld intersect(line l1, line l2){
    return (l1.b-l2.b)/(l2.k-l1.k);
}

inline bool to_erase(line l1, line l2, line l3){
    //ld x = intersect(l1, l3);
    //return l2.eval(x) <= l3.eval(x);
    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 && to_erase(vec[(int)vec.size()-2], vec[(int)vec.size()-1], ln))
        vec.pop_back();
    vec.push_back(ln);
}

void rec(int n, int m){
    if (m == 0)
        return;
    for (int i = n-1; i >= 1; i--){
        if (dp[i][m-1] + (pref[n]-pref[i])*pref[i] == dp[n][m]){
            rec(i, m-1);
            cout << i << ' ';
            return;
        }
    }
}

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 = 0; i <= n; i++){
        for (int j = 1; j <= m; j++)
            dp[i][j] = -1e15;
    }
    for (int i = 1; i <= n; i++)
        insrt(line(pref[i], -(pref[i]*pref[i]), i));
    swp();
    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;
            dp[i][ii] = vecCur[pos].eval(pref[i]);
            //cout << i << ' ' << ii << ' ' << pos << ' ' << vecCur[pos].k << ' ' << vecCur[pos].b << endl;
            insrt(line(pref[i], dp[i][ii]-(pref[i]*pref[i]), i));
        }
        swp();
    }
    cout << dp[n][m] << endl;
    rec(n, m);

}

/**

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