Submission #612180

#	Time	Username	Problem	Language	Result	Execution time	Memory
612180		nohaxjustsoflo	Split the sequence (APIO14_sequence)	C++17	100 / 100	896 ms	82176 KiB

sequence

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+1;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const ll inf=1e18;
const int K=600;
ll dp[mxN], dp2[mxN], a[mxN], p[mxN];
ll cost(int l, int r)
{
    if(l>r) return 0;
    return (p[r]-p[l])*(p[r]-p[l]);
}
int pos[200][mxN];
void solve(int l, int r, int optl, int optr, int layer)
{
    if(l>r) return;
    int m=(l+r)/2, opt=m-1;
    ll best=dp[m];
    for(int k=optl; k<=min(m-1,optr); k++)
    {
        ll cur=dp[k]+cost(k,m);
        if(cur<=best)
        {
            best=cur;
            opt=k;
        }
    }
    dp2[m]=best;
    pos[layer][m]=opt;
    solve(l,m-1,optl,opt,layer);
    solve(m+1,r,opt,optr,layer);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k; cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) p[i]=a[i]+p[i-1];
    for(int i=1; i<=n; i++) dp[i]=p[i]*p[i];
    for(int i=0; i<k; i++)
    {
        solve(1,n,1,n,i);
        for(int i=1; i<=n; i++) dp[i]=dp2[i];
    }
    cout << (p[n]*p[n]-dp[n])/2 << "\n";
    vector<int> ans;
    int x=n;
    while(~--k)
    {
        ans.push_back(pos[k][x]);
        x=pos[k][x];
    }
    reverse(ans.begin(),ans.end());
    for(int i:ans) cout << i << " ";
    cout << "\n";
}
/*
7 3
4 1 3 4 0 2 3
*/

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