Submission #919438

#	Time	Username	Problem	Language	Result	Execution time	Memory
919438		aykhn	Split the sequence (APIO14_sequence)	C++17	100 / 100	909 ms	86944 KiB

sequence

#include <bits/stdc++.h>
 
// author: aykhn
 
using namespace std;
typedef long long ll;
 
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
 
const int MXN = 1e5 + 5, MXK = 2e2 + 5;
 
int n, k;
ll a[MXN], pref[MXN];
int par[MXN][MXK];
ll l[MXN], r[MXN];
 
ll intersection(ll k1, ll b1, ll k2, ll b2)
{
    int neg = ((b2 - b1 < 0) ^ (k1 - k2 < 0));
    ll a = abs(b2 - b1);
    ll b = abs(k1 - k2);
    ll i = a / b;
    if (neg) i = -i;
    else if (a % b) i = i + 1;
    return i;
}
 
ll comp(ll k1, ll b1, ll k2, ll b2, int ind)
{
    if (k1 == k2) return b2 >= b1;
    ll i = intersection(k1, b1, k2, b2);
    return i <= l[ind];
}
 
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    k++;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    vector<ll> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) dp[i] = pref[i] * (pref[n] - pref[i]);
    for (int j = 2; j <= k; j++)
    {
        vector<ll> ndp(n + 1, 0);
        vector<int> st;
        for (int i = 1; i <= n; i++)
        {
            if (i > 1)
            {
                ll x = pref[i] - pref[n];
                int lx = 0;
                int rx = (int)st.size() - 1;
                while (lx < rx)
                {
                    int mid = (lx + rx + 1) >> 1;
                    if (l[mid + 1] <= x) lx = mid;
                    else rx = mid - 1;
                }
                int k1 = st[lx];
                ndp[i] = pref[k1] * (pref[i] - pref[n]) + dp[k1] + pref[i] * pref[n] - pref[i] * pref[i];
                par[i][j] = k1;
            }
            while (!st.empty() && comp(pref[st.back()], dp[st.back()], pref[i], dp[i], st.size()))
            {
                st.pop_back();
            }
            if (st.empty())
            {
                l[1] = -infll;
                r[1] = infll;
            }
            else
            {
                r[st.size()] = intersection(pref[st.back()], dp[st.back()], pref[i], dp[i]) - 1;
                l[st.size() + 1] = r[st.size()] + 1;
                r[st.size() + 1] = infll;
            }
            st.push_back(i);
        }
        swap(dp, ndp);
    }
    cout << dp[n] << '\n';
    int x = n;
    int y = k;
    vector<int> v;
    while (y > 1)
    {
        x = par[x][y];
        y--;
        v.pb(x);
    }
    sort(all(v));
    for (int x : v) cout << x << ' ';
    cout << '\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