Submission #308806

#	Time	Username	Problem	Language	Result	Execution time	Memory
308806		jainbot27	Split the sequence (APIO14_sequence)	C++17	100 / 100	1710 ms	82296 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int mxK = 201;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
ll dp[2][mxN]; int L[mxN][mxK]; ll p[mxN], a[mxN], n, K;
void divi(int k, int l, int r, int opt_l, int opt_r){
    if(l > r) return;
    int m = (l+r)/2;
    int pos = opt_l; ll ma = -infLL;
    for(int i = opt_l; i <= min(m-1, opt_r); i++){
        if(ckmax(ma, 1LL*dp[0][i]+1LL*(p[m]-p[i])*p[i])){
            pos = i;
        }
    }
    dp[1][m] = ma;
    L[m][k] = pos;
    divi(k, l, m-1, opt_l, pos);
    divi(k, m+1, r, pos, opt_r);
}


int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> K;
    FOR(i, 1, n+1){
        cin >> a[i];
        p[i] = a[i] + p[i-1];
    }
    if(n==2){
        assert(K==1);
        cout << a[1]*a[2] << nl;
        cout << 1 << nl;
        return 0;
    }
    ll bst = 0, val = 0;
    FOR(i, 1, K+1){
        divi(i, 1, n, 1, n);
        FOR(j, 1, n+1) dp[0][j] = dp[1][j];
        // cout << nl;
        if(i==K){
            FOR(j, 1, n+1){
                if(ckmax(val, dp[0][j])){
                    bst = j;
                }
            }
        }
    }
    vi res;
    cout << val << nl;
    int k = K; 
    while(k>0){
        res.pb(L[bst][k]);
        bst = L[bst][k];
        k--;
    }
    // cout << L[bst][1] << nl;
    // assert(siz(res)==K);
    trav(x, res){
        cout << x << ' ';
    }
    cout << nl;
}

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