Submission #1326689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326689		hoangtien69	Split the sequence (APIO14_sequence)	C++20	100 / 100	553 ms	82372 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const long long NEG_INF = LLONG_MIN;

int n, k;
long long a[MAXN];
long long pre[MAXN], suf[MAXN];
long long dp_prev[MAXN], dp_cur[MAXN];
int par[205][MAXN];
vector<int> trace;

struct Line
{
    long long m, b;
    int id;
};
struct CHT
{
    deque<Line> dq;

    bool bad(const Line &l1, const Line &l2, const Line &l3)
    {
        __int128 left  = (__int128)(l3.b - l1.b) * (l1.m - l2.m);
        __int128 right = (__int128)(l2.b - l1.b) * (l1.m - l3.m);
        return left >= right;
    }

    void add(long long m, long long b, int id)
    {
        Line ln = {m, b, id};
        while (dq.size() >= 2 &&
               bad(dq[dq.size()-2], dq.back(), ln))
            dq.pop_back();
        dq.push_back(ln);
    }

    pair<long long,int> query(long long x)
    {
        while (dq.size() >= 2 &&
               dq[0].m * x + dq[0].b <= dq[1].m * x + dq[1].b)
            dq.pop_front();
        return {dq[0].m * x + dq[0].b, dq[0].id};
    }

    bool empty()
    {
        return dq.empty();
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + a[i];
    for (int i = n; i >= 1; --i)
        suf[i] = suf[i + 1] + a[i];
    for (int i = 0; i <= n; ++i)
        dp_prev[i] = NEG_INF;
    for (int i = 1; i <= n - 1; ++i)
        dp_prev[i] = pre[i] * suf[i + 1];
    if (k == 1)
    {
        long long ans = NEG_INF;
        int pos = 0;

        for (int i = 1; i <= n - 1; ++i)
        {
            if (dp_prev[i] > ans)
            {
                ans = dp_prev[i];
                pos = i;
            }
        }
        cout << ans << "\n";
        cout << pos << "\n";
        return 0;
    }
    for (int t = 2; t <= k; ++t)
    {
        CHT cht;
        for (int i = 0; i <= n; ++i)
            dp_cur[i] = NEG_INF;
        for (int i = 1; i <= n - 1; ++i)
        {
            if (i - 1 >= t - 1 && dp_prev[i - 1] != NEG_INF)
            {
                cht.add(-pre[i - 1], dp_prev[i - 1], i - 1);
            }
            if (i >= t && !cht.empty())
            {
                auto res = cht.query(suf[i + 1]);
                dp_cur[i] = res.first + suf[i + 1] * pre[i];
                par[t][i] = res.second;
            }
        }
        for (int i = 0; i <= n; ++i)
            dp_prev[i] = dp_cur[i];
    }
    long long ans = NEG_INF;
    int pos = 0;
    for (int i = k; i <= n - 1; ++i)
    {
        if (dp_prev[i] > ans)
        {
            ans = dp_prev[i];
            pos = i;
        }
    }
    cout << ans << "\n";
    int cur = pos;
    for (int t = k; t >= 1; --t)
    {
        trace.push_back(cur);
        if (t > 1)
            cur = par[t][cur];
    }
    reverse(trace.begin(), trace.end());
    for (int v : trace)
        cout << v << " ";
}

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