Submission #1037180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037180		Phuoc	Split the sequence (APIO14_sequence)	C++14	22 / 100	48 ms	8284 KiB

sequence

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = 998244353;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 100010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int n, k;
long long a[MAX], sum[MAX];

void init(){
    cin >> n >> k;
    FOR(i, 1, n){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
}

pair <int, int> trace[55][55][55];
long long dp[55][55][55];

long long Try(int L, int R, int K){
    if(K == 0) return 0;
    if(L == R) return 0;
    if(dp[L][R][K] != -1) return dp[L][R][K];
    
    long long res = -INF;
    long long sumTotal = sum[R] - sum[L - 1], sumLeft = 0;
    FOR(i, L, R - 1){
        sumLeft += a[i];
        FOR(k1, 0, K - 1){
            int k2 = K - k1 - 1;
            if(k2 < 0) return 0;
            long long splitCost = sumLeft * (sumTotal - sumLeft);
            long long left = Try(L, i, k1);
            long long right = Try(i + 1, R, k2);
            long long cur = left + right + splitCost;
            if(maximize(res, cur)) trace[L][R][K] = make_pair(i, k1);
        } 
    }

    return dp[L][R][K] = res;
}

vector <int> path;

void backTrack(int L, int R, int K){
    if(K == 0) return;
    if(L >= R) return;

    int t = trace[L][R][K].fi;
    int k1 = trace[L][R][K].se;
    int k2 = K - k1 - 1;

    path.push_back(t);
    backTrack(L, t, k1);
    backTrack(t + 1, R, k2);
}

void solve(){
    memset(dp, -1, sizeof dp);
    cout << Try(1, n, k) << el;
    backTrack(1, n, k);
    sort(path.begin(), path.end());
    for(int x:path) cout << x << ' ';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        solve();
    }
    
    return 0;
}


 
/*** ROAD TO VOI 2025 ***/

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