Submission #1150378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150378		hahahoang132	Split the sequence (APIO14_sequence)	C++20	100 / 100	893 ms	87412 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e5 + 5;
const ll base = 37;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;
#define bit(x,y) ((x >> y) & 1)
struct ConvexHullTrick {
    const ll Inf = 1e18;

    ll n;
    ll a[N], b[N], id[N];

    vector<ll> line;
    vector<ld> poll;

    ConvexHullTrick() {
        poll.emplace_back(-Inf);
    }

    void clea()
    {
        line.clear();
        poll.clear();
        poll.emplace_back(-Inf);
    }

    ld ff(ll x, ll y) {
        return (ld) 1.0 * (b[x] - b[y]) / (a[y] - a[x]);
    }

    void Add(ll i) {
        while (!line.empty()) {
            if (a[line.back()] == a[i]) {
                if (b[line.back()] < b[i]) {
                    break;
                } else {

                    line.pop_back();
                    if (!line.empty()) {
                        poll.pop_back();
                    }
                }
            } else {
                if (line.size() < 2) {
                    break;
                }

                if (ff(i, line[line.size() - 2]) < ff(i, line.back())) {
                    break;
                } else {
                    line.pop_back();

                    if (!line.empty()) {
                        poll.pop_back();
                    }
                }
            }
        }

        if (line.empty() || a[line.back()] != a[i]) {
            if (!line.empty()) {
                poll.emplace_back(ff(i, line.back()));
            }

            line.emplace_back(i);
        }
    }

    pair<ll,ll> get(ll x) {
        ll j = upper_bound(poll.begin(), poll.end(), (ld) x) - poll.begin() - 1;

        return {a[line[j]] * x + b[line[j]],id[line[j]]};
    }
};

ll a[N],s[N];
ll d[2][N];
int v[205][N];
ConvexHullTrick f;
int main()
{
    ll n,k;
    cin >> n >> k;
    ll i,j;
    for(i = 1;i <= n;i++) cin >> a[i];
    for(i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];
    f.n = n + 5;
    ll e = 0;
    for(i = 2;i <= k + 1;i++)
    {
        f.clea();
        for(j = i;j <= n;j++)
        {
            f.a[j - i + 1] = s[j - 1];
            f.b[j - i + 1] = d[e][j - 1] - (s[j - 1] * s[j - 1]);
            f.id[j - i + 1] = j - 1;
            f.Add(j - i + 1);
            pair<ll,ll> tmp = f.get(s[j]);
            d[1 - e][j] = tmp.first;
            v[i][j] = tmp.second;
        }
        e = 1 - e;
    }
    cout << d[e][n] << "\n";
    i = k + 1;
    j = n;
    while(i > 1)
    {
        cout << v[i][j] << " ";
        j = v[i][j];
        i--;
    }
}

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