Submission #678856

#	Time	Username	Problem	Language	Result	Execution time	Memory
678856		Romiros	Split the sequence (APIO14_sequence)	C++17	100 / 100	1033 ms	89472 KiB

sequence

#include <bits/stdc++.h>
 
#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2", "popcnt")
 
using namespace std;
 
ll divide(ll a, ll b){
    if (b == 0){
        if (a > 0){
            return 1e18;
        }
        if (a < 0){
            return -1e18;
        }
        return 0;
    }
    ll d = 0;
    if (a % b){
        d = 1;
    }
    if ((a > 0 && b > 0) || (a < 0 && b < 0)){
        return (a / b) + d;
    }
    return -(abs(a) / abs(b));
}

struct Line{
    ll k = 0, b = -1e18, id = -1;
 
    Line(ll k, ll b, ll id) : k(k), b(b), id(id){}
 
    ll operator()(ll x){
        return k * x + b;
    }

    ll isect(const Line& a){
        return divide(a.b - b, k - a.k);
    }
};
 
struct LiChao{
    int sz;
    vector<Line> tree;
    vector<ll> uniq;
 
    LiChao(vector<ll> a){
        int n = a.size();
        sz = 1;
        while (sz < 2 * n){
            sz *= 2;
        }
        tree.resize(sz, {0, -(ll)1e18, -1});
        uniq = a;
        assert(is_sorted(all(a)));
        uniq.erase(unique(all(uniq)), uniq.end());
        while (uniq.size() < sz / 2){
            uniq.push_back(uniq.back() + 1);
        }
    }
 
    void clear(){
        for (int v = 0; v < sz; v++){
            tree[v].k = 0;
            tree[v].b = -1e18;
            tree[v].id = -1;
        }
    }
 
    void insert(int v, int tl, int tr, Line q){
        int tm = (tl + tr) / 2;
        bool l = (tree[v](uniq[tl]) < q(uniq[tl]));
        bool m = (tree[v](uniq[tm]) < q(uniq[tm]));
        if (m){
            swap(tree[v], q);
        }
        if (tl == tm){
            return;
        }
        if (l == m){
            insert(v * 2 + 1, tm + 1, tr, q);
        } else {
            insert(v * 2, tl, tm, q);
        }
    }
 
    void insert(Line q){
        insert(1, 0, sz / 2 - 1, q);
    }
 
    pair<ll, ll> get(int v, int tl, int tr, ll x){
        if (tl == tr){
            return {tree[v](x), tree[v].id};
        }
        int tm = (tl + tr) / 2;
        if (x <= uniq[tm]){
            return max(pair<ll, ll>{tree[v](x), tree[v].id}, get(v * 2, tl, tm, x));
        } else {
            return max(pair<ll, ll>{tree[v](x), tree[v].id}, get(v * 2 + 1, tm + 1, tr, x));
        }
    }
 
    pair<ll, ll> get(ll x){
        return get(1, 0, sz / 2 - 1, x);
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--){
        int n, k;
        cin >> n >> k;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        vector<ll> pref(n + 1);
        for (int i = 1; i <= n; i++){
            pref[i] = pref[i - 1] + a[i];
        }
        vector<ll> dp0(n + 1);
        vector<ll> dp1(n + 1, -1e18);
        vector<vector<int>> p(n + 1, vector<int>(k + 1));
        vector<Line> st;
        vector<double> from;
        for (int cnt = 1; cnt <= k; cnt++){
            st.clear();
            from.clear();
            dp1.assign(n + 1, -1e18);
            for (int i = 1; i <= n; i++){
                if (!st.empty()){
                    Line l = st[(int)(upper_bound(all(from), pref[i - 1]) - from.begin()) - 1];
                    int j = l.id;
                    ll val = l(pref[i - 1]);
                    dp1[i] = -(pref[i - 1] * pref[i - 1]) + pref[n] * pref[i - 1] + val;
                    p[i][cnt] = j;
                }
                if (dp0[i] != -1e18){
                    Line l = {pref[i - 1], dp0[i] - pref[n] * pref[i - 1], i};
                    while (st.size() > 1 && l.isect(st.back()) < st.back().isect(st[st.size() - 2])){
                        st.pop_back();
                        from.pop_back();
                    }
                    st.push_back(l);
                    if (st.size() == 1){
                        from.push_back(-1e9);
                    } else {
                        from.push_back(l.isect(st[st.size() - 2]));
                    }
                }
                // for (int j = i - 1; j >= 1; j--){
                //     if (dp[j][cnt - 1] != -1e18 && 
                //         dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]) >= dp[i][cnt]){
                //         p[i][cnt] = j;
                //         dp[i][cnt] = max(dp[i][cnt], dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]));
                //     }
                // }
            }
            dp0.swap(dp1);
        }
        int v = 1;
        for (int i = 1; i <= n; i++){
            if (dp0[i] > dp0[v]){
                v = i;
            }
        }
        cout << dp0[v] << "\n";
        vector<int> res;
        for (int cnt = k; cnt >= 1; cnt--){
            res.push_back(v);
            v = p[v][cnt];
        }
        reverse(all(res));
        for (int i = 0; i < k; i++){
            cout << res[i] - 1 << " ";
        }
        cout << "\n";
        // cout << dp[1][n][k] << "\n";
        // vector<int> res;
        // queue<array<int, 3>> q;
        // q.push({1, n, k});
        // while (!q.empty()){
        //     array<int, 3> t = q.front();
        //     q.pop();
        //     pair<int, int> w = p[t[0]][t[1]][t[2]];
        //     res.push_back(w.first);
        //     if (t[2]){
        //         q.push({t[0], w.first, w.second});
        //         q.push({w.first + 1, t[1], t[2] - 1 - w.second});
        //     }
        // }
        // assert(!res.empty());
        // sort(all(res));
        // for (int i = 0; i < res.size(); i++){
        //     if (res[i]){
        //         cout << res[i] << " "; 
        //     }
        // }
        // cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In constructor 'LiChao::LiChao(std::vector<long long int>)':
sequence.cpp:64:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         while (uniq.size() < sz / 2){
      |                ~~~~~~~~~~~~^~~~~~~~

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