Submission #715271

#	Time	Username	Problem	Language	Result	Execution time	Memory
715271		four_specks	Split the sequence (APIO14_sequence)	C++17	100 / 100	773 ms	98812 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename T>
    T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }

} // namespace

struct Line
{
    long m, c;
    int id;

    long operator()(long x) const { return m * x + c; }
};

long isect(const Line &l1, const Line &l2) { return fl_div(l1.c - l2.c, l2.m - l1.m); }

void solve()
{
    int n, k;
    cin >> n >> k, ++k;

    vector<long> a(n);
    for (long &x : a)
        cin >> x;

    vector<long> pref(n + 1);
    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + a[i];

    vector prv(n + 1, vector(k + 1, -1));
    vector<deque<Line>> dp(k + 1);

    dp[0].push_back({0, 0, 0});
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < min(k, i + 1); j++)
        {
            while ((int)dp[j].size() >= 2 && dp[j][1](pref[i + 1]) > dp[j][0](pref[i + 1]))
                dp[j].pop_front();
            prv[i + 1][j + 1] = dp[j][0].id;
            Line line = {pref[i + 1], dp[j][0](pref[i + 1]) - pref[i + 1] * pref[i + 1], i + 1};
            while ((int)dp[j + 1].size() >= 2 && line.m != dp[j + 1].back().m && isect(line, dp[j + 1].back()) <= isect(dp[j + 1].back(), dp[j + 1].end()[-2]))
                dp[j + 1].pop_back();
            if (dp[j + 1].empty() || line.m != dp[j + 1].back().m)
                dp[j + 1].push_back(line);
        }
    }

    long res = dp[k].back().c + pref[n] * pref[n];

    vector<int> pos;
    for (int i = prv[n][k], j = k; i > 0; i = prv[i][--j])
        pos.push_back(i);
    reverse(pos.begin(), pos.end());

    cout << res << '\n';
    for (int i : pos)
        cout << i << ' ';
    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    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