Submission #951715

#	Time	Username	Problem	Language	Result	Execution time	Memory
951715		Nelt	Split the sequence (APIO14_sequence)	C++17	100 / 100	1120 ms	85916 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll intersection(ll k, ll b, ll k1, ll b1)
{
    if (k == k1)
        return -1;
    return (ll)((b1 - b) / (k - k1 + 0.0));
}
void solve()
{
    ll n, k;
    cin >> n >> k;
    ll dp[2][n + 1], a[n + 1];
    int best[k + 1][n + 1];
    for (ll i = 0; i <= k; i++)
        for (ll j = 0; j <= n; j++)
            best[i][j] = 0;
    a[0] = 0;
    for (ll i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];
    for (ll i = 0; i <= n; i++)
        dp[0][i] = 0, dp[1][i] = -1e18;
    vector<array<ll, 3>> v;
    array<ll, 3> cur;
    for (ll i = 1; i <= k; i++)
    {
        v.clear();
        for (ll j = 0, pos; j < n; j++)
        {
            cur = {0, (ll)1e9, j};
            while (!v.empty() and v.back()[0] * a[v.back()[2]] + dp[(i + 1) & 1][v.back()[2]] - a[v.back()[2]] * a[n] < v.back()[0] * a[j] + dp[(i + 1) & 1][j] - a[j] * a[n])
                v.pop_back();
            if (v.empty())
                v.push_back({0, (ll)1e9, j});
            else
            {
                ll point = intersection(a[v.back()[2]], dp[(i + 1) & 1][v.back()[2]] - a[v.back()[2]] * a[n], a[j], dp[(i + 1) & 1][j] - a[j] * a[n]);
                if (point != -1)
                    v.back()[1] = point, cur[0] = point + 1, v.push_back(cur);
            }
            pos = upper_bound(v.begin(), v.end(), array<ll, 3>{a[j], (ll)1e18, (ll)1e18}) - v.begin();
            if (n > 200)
            {
                for (ll m = max(0ll, pos - 1); m <= min((ll)v.size() - 1, pos + 1); m++)
                    if (dp[i & 1][j] <= dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j]))
                        dp[i & 1][j] = dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j]), best[i][j] = v[m][2];
            }
            else
            {
                best[i][j] = 1;
                for (ll m = 0; m < j; m++)
                    if (dp[i & 1][j] <= dp[(i + 1) & 1][m] + (a[j] - a[m]) * (a[n] - a[j]))
                        dp[i & 1][j] = dp[(i + 1) & 1][m] + (a[j] - a[m]) * (a[n] - a[j]), best[i][j] = m;
            }
        }
    }
    pair<ll, ll> ans = make_pair(-1, 0);
    for (ll i = 1; i < n; i++)
        ans = max(ans, make_pair(dp[k & 1][i], i));
    cout << ans.first << endl;
    ll x = ans.second;
    for (ll i = k; i >= 1; i--)
        cout << x << " ", x = best[i][x];
    cout << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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