Submission #1208755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208755		jahongir	Split the sequence (APIO14_sequence)	C++20	100 / 100	1085 ms	81464 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
                    tree_order_statistics_node_update>;

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()

const int mxn = 1e5+10;
const ll  inf = 1e18;
ll arr[mxn];

vector<ll> dp(mxn), dp2(mxn);
int suc[mxn][201];

void daq(int l, int r, int opl, int opr, int k){
    if(r < l) return;
    int m = (l+r)>>1;
    
    pair<ll,int> best = {inf,-1};
    for(int i = opl; i <= min(m,opr); i++)
        best = min(best,{dp[i]+(arr[m]-arr[i])*(arr[m]-arr[i]),i});
    
    suc[m][k] = best.second;
    dp2[m] = best.first;

    daq(l,m-1,opl,suc[m][k],k);
    daq(m+1,r,suc[m][k],opr,k);
}

void solve(){
    int n,k; cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> arr[i]; arr[i] += arr[i-1];
        dp[i] = arr[i]*arr[i];
    }
    dp[0] = 0;

    for(int i = 1; i <= k; i++){
        daq(i,n,i,n,i); dp = dp2;
    }

    cout << (arr[n]*arr[n] - dp[n])/2 << '\n';

    int u = n, cnt = k;
    vector<int> res;
    while(k){
        res.pb(suc[u][k]);
        u = suc[u][k]; k--;
    }

    reverse(all(res));
    for(auto x : res) cout << x << ' ';
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while(t--) solve();
}

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