Submission #989621

#	Time	Username	Problem	Language	Result	Execution time	Memory
989621		trucmai	Split the sequence (APIO14_sequence)	C++17	100 / 100	1116 ms	86156 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include "bits/tools.h"
    #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
    #define debug(x...)
#endif
#define ll long long
#define endl '\n'

const int N = 1e5 + 3,LOG = 27,MOD = 1e9 + 7; 
const ll INF = 1e18;
int n,k;
ll a[N],pf[N],dp[2][N];
ll cost(int l,int r){
    if(l > r) swap(l,r);
    return (pf[r] - pf[l - 1])*pf[l - 1];
    // return (pf[r] - pf[l - 1])*(pf[n] - pf[r]);
}
/*
    dp[i][j] is the maximum at position j and already had j paritions 
    dp[i][j] = max(dp[k][j - 1] + cost(k,i))
    cost(l,r) = sum(l,r)*sum(r+1,n)
              = (pf[r] - pf[l - 1])*(pf[n] - pf[r])   
*/
int trace[N][210];
void calc(int l,int r,int ql,int qr,int j){
    if(l > r) return;
    int mid = (r+l) >> 1; 
    pair<ll,int> res = {-INF,-1};
    for(int i = ql;i <= min(mid,qr);++i)
        res = max(res,{dp[(j&1)^1][i - 1] + cost(i,mid),i});
    dp[j&1][mid] = res.first; 
    trace[mid][j] = res.second - 1; 
    calc(l,mid-1,ql,res.second,j);
    calc(mid+1,r,res.second,qr,j);
}
void solver(){
    cin>>n>>k;
    for(int i = 1;i <= n;++i){
        cin>>a[i];
        pf[i] = pf[i - 1] + a[i];
    }
    for(int i = 1;i <= k;++i) calc(1,n,1,n,i);
    cout<<dp[k&1][n]<<endl;
    int ptr = n; vector<int>path; 
    for(int i = k;i >= 1;--i){
        ptr = trace[ptr][i];  
        path.push_back(ptr);
    }
    reverse(path.begin(),path.end());
    for(auto i : path) cout<<i<<" ";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0); 
    int t = 1; //cin>>t; 
    while(t--) solver();
}

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