Submission #147150

#	Time	Username	Problem	Language	Result	Execution time	Memory
147150		jh05013	Split the sequence (APIO14_sequence)	C++17	100 / 100	1574 ms	87096 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define entire(X) X.begin(),X.end()
#define dbgv(V) for(auto x:V)cout<<x<<' ';cout<<endl;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

template <typename T>
struct CHT{
    vector<tuple<T,T,int>> hull; int p=0;
    long double cr(int x){
        auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1];
        return (long double)(by-bx) / (ax-ay);
    }

    void insert(T a, T b, int i){
        if(!hull.empty()){
            auto [aa,bb,_] = hull.back();
            if(aa == a && bb <= b) return;
            if(aa == a) hull.pop_back();
        }
        hull.push_back({a,b,i});
        while(hull.size() > 2 && cr(hull.size()-3) >
            cr(hull.size()-2)) hull.erase(hull.end()-2);
    }

    pair<T,int> get(T x){
        while(p+1 < hull.size() && cr(p) <= x) p++;
        auto [a,b,i] = hull[p];
        return {a*x + b, i};
    }
};

ll DP[2][100005], S[100005];
int prv[202][100005];
int main(){OJize();
    int n, k; cin>>n>>k; k++;
    for(int i=0; i<n; i++){
        ll x; cin>>x;
        S[i+1] = S[i] + x;
    }

    for(int j=2; j<=k; j++){
        CHT<ll> cht;
        cht.insert(-S[j-1], S[j-1]*S[j-1]-DP[1-j%2][j-1], j-1);
        for(int i=j; i<=n; i++){
            auto [val,idx] = cht.get(S[i]);
            DP[j%2][i] = -val, prv[j][i] = idx;
            cht.insert(-S[i], S[i]*S[i]-DP[1-j%2][i], i);
        }
    }
    
    cout << DP[k%2][n] << '\n';
    vector<int> trace;
    int last = n;
    while(k >= 2){
        last = prv[k--][last];
        trace.push_back(last);
    }
    reverse(entire(trace));
    dbgv(trace);
}

Compilation message (stderr)

sequence.cpp: In instantiation of 'void CHT<T>::insert(T, T, int) [with T = long long int]':
sequence.cpp:45:62:   required from here
sequence.cpp:18:26: warning: unused variable '_' [-Wunused-variable]
             auto [aa,bb,_] = hull.back();
                          ^
sequence.cpp: In instantiation of 'std::pair<_BiIter, int> CHT<T>::get(T) [with T = long long int]':
sequence.cpp:47:42:   required from here
sequence.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p+1 < hull.size() && cr(p) <= x) p++;
sequence.cpp: In instantiation of 'long double CHT<T>::cr(int) [with T = long long int]':
sequence.cpp:23:36:   required from 'void CHT<T>::insert(T, T, int) [with T = long long int]'
sequence.cpp:45:62:   required from here
sequence.cpp:12:22: warning: unused variable '_' [-Wunused-variable]
         auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1];
                      ^
sequence.cpp:12:49: warning: unused variable '__' [-Wunused-variable]
         auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1];
                                                 ^

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