| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 398991 | cpp219 | Split the sequence (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std::chrono_literals;
const ll N = 1e5 + 6;
const ll lim = 3e5 + 6;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
ll n,a[N],b[N],dp[N],k,val[N],pre[N];
int best[211][N];
ll sum(ll L,ll R){
return b[R] - b[L - 1];
}
ll cal(ll x,ll y){
return sum(1,x - 1) * sum(x,y);
}
void f(ll rm,ll L,ll R,ll lf,ll rg){
if (L > R) return;
ll chosen = 0,cur = (L + R)/2,mx = -inf;
for (ll i = lf;i <= min(rg,cur);i++){
if (rm - 1 >= i - 1) continue;
ll now = pre[i - 1] + cal(i,cur);
if (now > mx){
mx = now; chosen = i;
}
}
best[rm][cur] = chosen; val[cur] = mx;
f(rm,L,cur - 1,lf,chosen); f(rm,cur + 1,R,chosen,rg);
}
void Trace(ll k,ll n){
if (!k) return;
ll p = best[k][n];
cout<<p - 1<<" "; Trace(k - 1,p - 1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "60"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
std::this_thread::sleep_for(-9999999ms);
cin>>n>>k;
for (ll i = 1;i <= n;i++) cin>>a[i],b[i] = b[i - 1] + a[i];
for (ll i = 1;i <= k;i++){
f(i,1,n,1,n);
for (ll j = i + 1;j <= n;j++) dp[j] = pre[j] = val[j];
}
cout<<dp[n]<<"\n"; Trace(k,n);
}