Submission #383298

#	Time	Username	Problem	Language	Result	Execution time	Memory
383298		danielcm585	Split the sequence (APIO14_sequence)	C++14	0 / 100	77 ms	131076 KiB

sequence

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 1e3;
const int K = 2e2;
const ll INF = 1e18;
int n, k;
ll a[N+2], sum[N+2];
ll memo[N+2][N+2][K+2];
vector<int> res;

ll dp(int id, int ls, int seg) {
    if (id > n) return (seg == k ? 0 : -INF);
    if (memo[id][ls][seg] != -1) return memo[id][ls][seg];
    ll ret = dp(id+1,ls,seg);
    if (seg+1 <= k) ret = max(ret,dp(id+1,id,seg+1));
    ret += a[id]*sum[ls];
    return memo[id][ls][seg] = ret;
}

void bt(int id, int ls, int seg) {
    if (id > n) return;
    if (dp(id,ls,seg) == dp(id+1,id,seg+1)+a[id]*sum[ls]) {
        res.push_back(id);
        bt(id+1,id,seg+1);
    }
    else bt(id+1,ls,seg);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1]+a[i];
    }
    memset(memo,-1,sizeof(memo));
    bt(1,0,0);
    cout << dp(1,0,0) << '\n';
    for (int i = 0; i < k; i++) {
        if (i != 0) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

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