Submission #1150156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150156		cpismylifeOwO	Split the sequence (APIO14_sequence)	C++20	100 / 100	965 ms	87772 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const long long inf = -1e18;
const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;

int n, k;
long long arr[MaxN];

void Inp()
{
    cin >> n >> k;
    k++;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
}

struct Line
{
    long long a, b;
    int id;

    Line() = default;

    Line(long long _a, long long _b, int _id)
    {
        a = _a;
        b = _b;
        id = _id;
    }
};

vector<Line> hull;
vector<long double> intersect;

bool Check(const Line& a, const Line& b, const Line& c)
{
    return (long double)(c.b - a.b) / (long double)(a.a - c.a) > (long double)(b.b - a.b) / (long double)(a.a - b.a);
}

void Reset()
{
    hull.clear();
    intersect.clear();
}

void Add(const Line& k)
{
    if (!hull.empty() && hull.back().a == k.a)
    {
        if (hull.back().b < k.b)
        {
            hull.pop_back();
            intersect.pop_back();
            while ((int)hull.size() >= 2)
            {
                Line p = hull.back();
                hull.pop_back();
                if (Check(hull.back(), p, k))
                {
                    hull.push_back(p);
                    break;
                }
                intersect.pop_back();
            }
            if (!hull.empty())
            {
                intersect.pop_back();
                intersect.push_back((long double)((long double)(k.b - hull.back().b) / (long double)(hull.back().a - k.a)));
            }
            hull.push_back(k);
            intersect.push_back(-inf);
        }
        return;
    }
    while ((int)hull.size() >= 2)
    {
        Line p = hull.back();
        hull.pop_back();
        if (Check(hull.back(), p, k))
        {
            hull.push_back(p);
            break;
        }
        intersect.pop_back();
    }
    if (!hull.empty())
    {
        intersect.pop_back();
        intersect.push_back((long double)((long double)(k.b - hull.back().b) / (long double)(hull.back().a - k.a)));
    }
    hull.push_back(k);
    intersect.push_back(-inf);
}

pair<long long, int> Query(long long x)
{
    assert(!hull.empty());
    int p = upper_bound(intersect.begin(), intersect.end(), (long double)x) - intersect.begin();
    return make_pair(hull[p].a * x + hull[p].b, hull[p].id);
}

long long sum[MaxN];
int track[202][MaxN];
pair<long long, int> F[2][MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        sum[x] = sum[x - 1] + arr[x];
    }
    F[0][0] = make_pair(0, 0);
    for (int x = 1; x <= n; x++)
    {
        F[0][x] = make_pair(inf, 0);
    }
    for (int x = 1; x <= k; x++)
    {
        Reset();
        for (int y = 0; y < x; y++)
        {
            F[x & 1][y] = make_pair(inf, 0);
        }
        Add(Line(sum[x - 1], F[(x & 1) ^ 1][x - 1].first - sum[x - 1] * sum[x - 1], x - 1));
        for (int y = x; y <= n; y++)
        {
            F[x & 1][y] = Query(sum[y]);
            Add(Line(sum[y], F[(x & 1) ^ 1][y].first - sum[y] * sum[y], y));
        }
        for (int y = 0; y <= n; y++)
        {
            track[x][y] = F[x & 1][y].second;
        }
    }
    pair<long long, int> res = F[k & 1][n];
    cout << res.first << "\n";
    int cur = k;
    while (res.second > 0)
    {
        cout << res.second << " ";
        cur--;
        res.second = track[cur][res.second];
    }
}

int main()
{
    //freopen("B.INP", "r", stdin);
    //freopen("B.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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