Submission #1092263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092263		DangKhoizzzz	Split the sequence (APIO14_sequence)	C++14	11 / 100	2074 ms	117584 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pii;

const int maxn = 2e5 + 7;



int N , K , a[205] , ps[205] , f[205][205][205];
bool vis[205][205][205];


pair <int ,pair<int ,int>> trace[205][205][205];

int sum(int l , int r)
{
    return ps[r] - ps[l-1];
}


int solve(int l , int r , int k)
{
    if(k == 0) return 0ll;
    if(l > r) return -1e18;
    if(l == r) return -1e18;

    if(vis[l][r][k]) return f[l][r][k];

    vis[l][r][k] = 1;

    for(int j = l; j < r; j++)
    {
        for(int x = 0; x < k; x++)
        {
            int cal = solve(l , j , x) + solve(j+1 , r , k-x-1) + sum(l , j)*sum(j+1 , r);

            if(f[l][r][k] < cal)
            {
                trace[l][r][k].fi = j;
                trace[l][r][k].se.fi = x;
                trace[l][r][k].se.se = k - x - 1;

                f[l][r][k] = cal;
            }
        }
    }

    return f[l][r][k];
}


void dfstrace(int l, int r , int k)
{
    if(trace[l][r][k].fi == 0) return;


    cout << trace[l][r][k].fi << ' ';

    int j = trace[l][r][k].fi;

    dfstrace(l , j , trace[l][r][k].se.fi);
    dfstrace(j+1 , r , trace[l][r][k].se.se);
}


void data()
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++) cin >> a[i];

    for(int i = 1; i <= N; i++) ps[i] = ps[i-1] + a[i];

    cout << solve(1 , N , K) << '\n';

    dfstrace(1 , N , K);
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    data();
    return 0;
}

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