Submission #90008

#	Time	Username	Problem	Language	Result	Execution time	Memory
90008		someone_aa	Split the sequence (APIO14_sequence)	C++17	50 / 100	493 ms	8144 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 1100;
const int maxk = 210;
ll dp[maxn][maxk];
ll arr[maxn], sum[maxn];
ll point[maxn][maxk];
ll n, k;

ll recursion(ll i, ll g) {
    if(g == -1 || i > n) return 0LL;
    if(dp[i][g] != -1) return dp[i][g];
    ll temp = 0LL, splitpoint = 0;
    for(int j=i;j<=n;j++) {
        ll cost = sum[i-1] * (sum[j] - sum[i-1]);
       // temp = max(temp, recursion(j+1, g-1) + cost);

        ll curr = recursion(j+1, g-1) + cost;
        if(curr > temp) {
            temp = curr;
            splitpoint = j+1;
        }
    }
    point[i][g] = splitpoint;
    return dp[i][g] = temp;
}

int main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++) {
        sum[i] = sum[i-1] + arr[i];
    }
    memset(dp, -1, sizeof(dp));
    cout<<recursion(1, k)<<"\n";

    int pointnow = 1;
    for(int i=k;i>0;i--) {
        pointnow = point[pointnow][i];
        cout<<max(1, pointnow-1)<<"\n";
    }

    return 0;
}

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