Submission #36803

#	Time	Username	Problem	Language	Result	Execution time	Memory
36803		imaxblue	Split the sequence (APIO14_sequence)	C++14	100 / 100	1493 ms	93000 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<ll, ll>
#define p3i pair<pii, ll>
#define pll pair<ll, int>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009

int pre[100005][205], l2, n, k, a, p[205], lst;
ll ans=-1, t, psa[100005];
deque<pair<ll, int> > mon[205];
void out(int P, int K){
    if (K!=0) out(pre[P][K], K-1);
    printf("%i ", P);
}
ll cross(pll A, pll O, pll B){
    return (A.x-O.x)*(-psa[B.y]+psa[O.y])-(B.x-O.x)*(-psa[A.y]+psa[O.y]);
}
void add(ll K, pair<ll, int> P){
    while(mon[K].size()>p[K]+1 && cross(mon[K][mon[K].size()-2], mon[K].back(), P)<=0){
        mon[K].pop_back();
    }
    mon[K].pb(P);
}
int main(){
    mon[0].pb(mp(0, 0));
    cin >> n >> k;
    for (int l=1; l<=n; ++l){
        cin >> a; psa[l]=a+psa[l-1];
    }
    for (int l=1; l<=n; ++l){
        for (l2=k-1; l2>=0; --l2){
            if (mon[l2].empty()) continue;
            while(p[l2]+1<mon[l2].size() &&
                (psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]].y])+mon[l2][p[l2]].x<=
                (psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]+1].y])+mon[l2][p[l2]+1].x)
                mon[l2].pop_front();//, cout << "*";
            pre[l][l2]=mon[l2][p[l2]].y;
            t=(psa[n]-psa[l])*(psa[l]-psa[mon[l2][p[l2]].y])+mon[l2][p[l2]].x;
            //cout << t << ' ' ;
            if (l2==k-1 && t>ans){
                ans=t; lst=l;
            }
            add(l2+1, mp(t, l));
        }
        //cout << endl;
    }
    cout << ans << endl;
    if (lst!=-1) out(lst, k-1);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void add(long long int, std::pair<long long int, int>)':
sequence.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(mon[K].size()>p[K]+1 && cross(mon[K][mon[K].size()-2], mon[K].back(), P)<=0){
                        ^
sequence.cpp: In function 'int main()':
sequence.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(p[l2]+1<mon[l2].size() &&
                          ^

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