Submission #851730

#	Time	Username	Problem	Language	Result	Execution time	Memory
851730		treap_enjoyer	Split the sequence (APIO14_sequence)	C++14	78 / 100	856 ms	96056 KiB

sequence

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = 1e18;
const int MAXN = 1e5 + 5;

struct line{
    ll k;
    ll c;
    ll num;
    ll calc(ll x){
        return k * x + c;
    }
    long double intersec(line b){
        if(k == b.k){
            if(c == b.c) return INF;
            else return -INF;
        }
        else return ((c - b.c) * 1.) / ((b.k - k) * 1.);
    }
};

vector<pair<line, ld> > st;
vector<ld> seg;
vector<line> seglines;
int cur;
int pos;
void add(line a){
    if(st.size() == 0){
        st.push_back({a, INF});
        //cout << st[st.size() - 1].first.c << " " << st[st.size() - 1].first.k << endl;
        seg[st.size()] = INF;
        seglines[st.size()] = a;
        pos = 1;
        return;
    }
    if(st.size() == 1){
        if(a.k == st.back().first.k){
            if(a.c > st.back().first.c){
                seglines[1] = a;
                st.back().first = a;
                //cout << st.back().first.k << " " << st.back().first.c << endl;
                return;
            }
        }
        else{
            ll pos = a.intersec(st.back().first);
            st.back().second = pos;
            seg[st.size()] = pos;
            st.push_back({a, INF});
            seg[st.size()] = INF;
            seglines[st.size()] = a;
            //cout << st[st.size() - 1].first.k << " " << st[st.size() - 1].first.c << endl;
            return;
        }
    }
    line b = st[st.size() - 1].first;
    if(a.k == b.k){
        if(a.c <= b.c) return;
        else{
            if(pos == st.size()){
                pos--;
            }
            st.pop_back();
            st.back().second = INF;
            seg[st.size()] = INF;
            add(a);
            return;
        }
    }
    else{
        st.pop_back();
        line c = st.back().first;
        if(a.intersec(c) <= st.back().second){
            //cout << a.k << " " << a.c << " -- " << b.k << " " << b.c << " --- " << c.k << " " << c.c << " " << a.intersec(c) << " " << st.back().second << endl;
            if(pos == st.size() + 1){
                pos--;
            }
            seg[st.size()] = INF;
            st.back().second = INF;
            add(a);
            return;  
        }
        else{
            ll x = a.intersec(b);
            if(pos == st.size() && x < cur){
                pos++;
            }
            st.push_back({b, x});
            seg[st.size()] = x;
            st.push_back({a, INF});
            seg[st.size()] = INF;
            seglines[st.size()] = a;
            return;
        }
    }
}
void upd(int x){
    while(seg[pos] < x){
        pos++;
    }
    cur = x;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<vector<ll> > dp(2, vector<ll>(n + 2, -INF));
    vector<vector<int> > p(k + 2, vector<int>(n + 2, 0));
    dp[1][0] = 0;
    vector<ll> pref(n + 2, 0);
    for(int i = 1; i <= n; i++){
        pref[i] += pref[i - 1];
        pref[i] += a[i];
    }
    for(int i = 1; i <= k + 1; i++){
        dp[0].swap(dp[1]);
        dp[1].assign(n + 1, 0);
        st.clear();
        seg.clear();
        seglines.clear();
        seg.resize(n + 1, INF);
        seglines.resize(n + 1);
        cur = pref[1];
        pos = 1; 
       // cout << i << ": " << endl;  
        for(int j = 1; j <= n; j++){
           // cout << pref[j - 1] << " <> " << dp[i - 1][j - 1] - pref[j - 1] * pref[j - 1] << endl;
            if(dp[0][j - 1] != -INF){
            add({pref[j - 1], dp[0][j - 1] - pref[j - 1] * pref[j - 1], j - 1});
            }
            upd(pref[j]);
            if(st.size() && seglines[pos].calc(pref[j]) > dp[1][j]){
                dp[1][j] = seglines[pos].calc(pref[j]);
                p[i][j] = seglines[pos].num;
            }
            /*for(int k = 0; k < st.size(); k++){
                cout << "(" << st[k].first.k << " + " << st[k].first.c << ")" << endl;
            }
            cout << "---------" << endl;*/ 
        }
    }
    vector<int> ans;
/*for(int i = 0; i <= k + 1; i++){
        for(int j = 0; j <= n; j++){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
    int cur = n;
    for(int i = k; i > 0; i--){
        ans.push_back(p[i + 1][cur]);
        cur = p[i + 1][cur];
    }
    cout << dp[1][n] << endl;
    reverse(all(ans));
    for(auto i: ans){
        cout << i << " ";
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void add(line)':
sequence.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             if(pos == st.size()){
      |                ~~~~^~~~~~~~~~~~
sequence.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             if(pos == st.size() + 1){
      |                ~~~~^~~~~~~~~~~~~~~~
sequence.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<line, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if(pos == st.size() && x < cur){
      |                ~~~~^~~~~~~~~~~~

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