Submission #919431

#	Time	Username	Problem	Language	Result	Execution time	Memory
919431		aykhn	Split the sequence (APIO14_sequence)	C++17	0 / 100	62 ms	131072 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 0x3F3F3F3F
#define bpc __builtin_popcount
 
const int MXN = 2e5 + 5, MXK = 3e2 + 5;
 
int n, k;
int a[MXN], pref[MXN];
int dp[MXN][MXK];
array<int, 2> par[MXN][MXK];
int l[MXN], r[MXN];
 
int intersection(int k1, int b1, int k2, int b2)
{
    int neg = ((b2 - b1 < 0) ^ (k1 - k2 < 0));
    int a = abs(b2 - b1);
    int b = abs(k1 - k2);
    int i = a / b;
    if (neg) i = -i;
    else if (a % b) i = i + 1;
    return i;
}
 
int comp(int k1, int b1, int k2, int b2, int ind)
{
    if (k1 == k2) return b2 >= b1;
    int 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];
    }
    for (int i = 1; i <= n; i++) dp[i][1] = pref[i] * (pref[n] - pref[i]);
    for (int j = 2; j <= k; j++)
    {
        vector<int> st;
        for (int i = 1; i <= n; i++)
        {
            if (i > 1)
            {
                int 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];
                dp[i][j] = pref[k1] * (pref[i] - pref[n]) + dp[k1][j - 1] + pref[i] * pref[n] - pref[i] * pref[i];
                par[i][j] = {k1, j - 1};
            }
            while (!st.empty() && comp(pref[st.back()], dp[st.back()][j - 1], pref[i], dp[i][j - 1], 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()][j - 1], pref[i], dp[i][j - 1]) - 1;
                l[st.size() + 1] = r[st.size()] + 1;
                r[st.size() + 1] = infll;
            }
            st.push_back(i);
        }
    }
    cout << dp[n][k] << '\n';
    int x = n;
    int y = k;
    vector<int> v;
    while (y > 1)
    {
        int x1 = par[x][y][0];
        int y1 = par[x][y][1];
        x = x1;
        y = y1;
        v.pb(x);
    }
    sort(all(v));
    for (int x : v) cout << x << ' ';
    cout << '\n';
}

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