Submission #1149796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149796		windowwife	Split the sequence (APIO14_sequence)	C++20	100 / 100	811 ms	83016 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 2, maxk = 202;
ll n, k, a, ps[maxn], dp[maxn][2], cur;
int track[maxn][maxk];
pair<ll, int> res = {0, 0};
vector<int> op;
struct Line
{
    ll x, y;
    int id;
};
deque<Line> hull;
bool check (const Line& A, const Line& B, const Line& C)
{
    ll p = (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
    return p >= 0;
}
void add (Line l)
{
    while (hull.size() >= 2 && check(hull[hull.size() - 2], hull.back(), l))
        hull.pop_back();
    hull.push_back(l);
}
pair<ll, int> query (int q)
{
    while (hull.size() >= 2 && hull.front().x*q + hull.front().y <= hull[1].x*q + hull[1].y) hull.pop_front();
    return {hull.front().x*q + hull.front().y, hull.front().id};
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        ps[i] = ps[i - 1] + a;
    }
    for (int i = 1; i < n; i++)
    {
        dp[i][1] = ps[i]*(ps[n] - ps[i]);
        track[i][1] = i;
    }
    for (int j = 2; j <= k; j++)
    {
        hull.clear();
        for (int i = 1; i < n; i++)
        {
            if (i > 1)
            {
                pair<ll, int> p = query(ps[i]);
                dp[i][j & 1] = p.first + ps[i]*(ps[n] - ps[i]);
                track[i][j] = p.second;
            }
            add({ps[i], dp[i][1 ^ (j & 1)] - ps[i]*ps[n], i});
        }
    }
    for (int i = 1; i < n; i++) res = max(res, {dp[i][k & 1], i});
    cur = res.second;
    for (int j = k; j >= 1; j--)
    {
        op.push_back(cur);
        cur = track[cur][j];
    }
    reverse(op.begin(), op.end());
    cout << res.first << '\n';
    for (int x : op) cout << x << " ";
}

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