Submission #1215104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215104		arkanefury	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define lb lower_bound
#define F first
#define S second
#define sz size()
#define int long long
#define all(v) v.begin(),v.end()
#define FOR1(x, n) for(int j = x; j <= n; j ++)
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N =  1e5+5;
int a[N], b[N], pref[N];
pair<int, int> dp[100005][205];
int n,m,k,sum=0,x,y, ans, r, cnt, l, mod = 1e9+7, inf = -1e18;
string s, str;
bool used[N];
struct kxt{
    int l, r, b, k, ind;
};
struct obtain{
    int k, b, ind;
};
vector<kxt>v;
void add(int b, int k, int po){
    while(v.sz){
        kxt i = *v.rbegin();
        if(k == i.k){
        if(b >= i.b)v.pop_back();
        else{
            return;
        }
        }
        else{
        int pl = ( i.b - b ) / ( k - i.k );
        if( pl >= i.r)v.pop_back();
        else{
            v.pop_back();
            v.pb({i.l, pl, i.b, i.k, i.ind});
            v.pb({pl+1, 10000000000, b, k, po});
            return;
        }
        }
    }
    v.pb({-10000000000, 10000000000, b, k, po});
}
obtain get( int pos, int l = 0, int r = v.sz-1){
    while(l <= r){
        int md = (l + r) >> 1;
        if(v[md].l <= pos)l = md + 1;
        else r = md - 1;
    }
    return {v[r].k, v[r].b, v[r].ind};
}
void solve(){
    cin >> n >> m;
    FOR(i, 1, n, 1)cin >> a[i], pref[i] = pref[i-1] + a[i];
    x = y = 0;
    int io;
    ans = -1e18;
    FOR(i, 1, n-1, 1){
        dp[i][1].F = (pref[n] - pref[i]) * pref[i];
        if(ans < dp[i][1].F)ans = max(ans, dp[i][1].F), io = i;
    }
    FOR(i, 2, m, 1){
        FOR(j, 1, i-1, 1)add(dp[j][i-1].F, pref[j], j);
        FOR(j, i, n-1, 1){
            obtain ok = get(pref[j]-pref[n]);
                cnt = ok.b + ok.k * (pref[j]-pref[n]) + pref[j] * (pref[n] -  pref[j]);
                // pref[n] * pref[j] - pref[n] * pref[ok] - pref[j] * pref[j] + pref[j] * pref[ok]
                // - pref[n] * pref[ok] + pref[j] * pref[ok]
                // pref[ok] * (pref[j] - pref[n])
                    dp[j][i].F = cnt, dp[j][i].S = ok.ind;
                    if(ans <= dp[j][i].F)ans = max(ans, dp[j][i].F), io = j;
                    add(dp[j][i-1].F, pref[j], j);
        }
        v.clear();
    }
    x = m;
    cout << ans << '\n';
    vector<int>lp;
    while(x > 0)lp.pb(io), io = dp[io][x].S, x --;
    FORR(i, lp.sz-1, 0, 1)cout << lp[i] << ' ';
}
signed main(){
    nikita
    int tt = 1;
    if(!tt)cin >> tt;
    FOR(i, 1, tt, 1)solve();
}

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