Submission #470598

#	Time	Username	Problem	Language	Result	Execution time	Memory
470598		ymm	Split the sequence (APIO14_sequence)	C++17	62 / 100	478 ms	85356 KiB

sequence

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 100'010;
const int K = 210;
ll dp0[N], dp1[N];
ll sum[K], pro[K];
int pre[K];
int sp[N][K];
ll a[N];
int n, k;

int main()
{
    FAST;
    cin >> n >> k;
    Loop(i,0,n) cin >> a[i];
    Loop(i,1,N) dp0[i] = 1e15;
    Loop(j,1,k+2)
    {
        dp1[0] = 0;
        Loop(i,0,n)
        {
            pro[j] += sum[j]*a[i], sum[j] += a[i];
            while(pre[j] < i && dp0[pre[j]] + pro[j] >= dp0[pre[j]+1] + (pro[j] - a[pre[j]]*(sum[j]-a[pre[j]])))
            {
                sum[j] -= a[pre[j]];
                pro[j] -= a[pre[j]]*sum[j];
                pre[j]++;
            }
            dp1[i+1] = dp0[pre[j]]+pro[j];
            sp[i+1][j] = pre[j];
        }
        Loop(i,0,N) dp0[i] = dp1[i];
    }
    ll sum = 0, sum2 = 0;
    Loop(i,0,n) sum += a[i], sum2 += a[i]*a[i];
    cout << (sum*sum-sum2)/2 - dp0[n] << '\n';
    vector<int> ans;
    for(int j = k+1; j >= 2; --j)
    {
        ans.push_back(sp[n][j]);
        n = sp[n][j];
    }
    reverse(all(ans));
    for(int x : ans) cout << x << ' ';
}

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