Submission #26426

#	Time	Username	Problem	Language	Result	Execution time	Memory
26426		WhipppedCream	Split the sequence (APIO14_sequence)	C++14	100 / 100	1629 ms	84836 KiB

sequence

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
int A[100005];
ll B[100005];
ll sum(int a, int b)
{
    return B[b] - B[a-1];
}
ll dp[2][100005];
int opt[205][100005];
void solve(int k, int L, int R, int i, int j)
{
    if(L> R) return;
    int M = (L+R)/2;
    ll best = -1e9;
    int add = 0;
    //printf("dp[%d][%d]:\n", k, M);
    for(int p = max(i, 2); p<= min(j, M); p++)
    {
        ll here = dp[1-k%2][p-1] + sum(1, p-1)*sum(p, M);
        //printf("p = %d %lld %lld = %lld\n", p, dp[k-1][p-1], sum(1, p-1)*sum(p, M), here);
        if(here> best)
        {
            best = here;
            add = p;
        }
    }
    dp[k%2][M] = best;
    opt[k][M] = add;
    //printf("dp[%d][%d] = %lld\n", k, M, best);
    solve(k, L, M-1, i, add);
    solve(k, M+1, R, add, j);
}
int main()
{
    //freopen("50", "r", stdin);
    //freopen("50.out", "w", stdout);
    int n, k; scanf("%d %d", &n, &k);
    k++;
    for(int i = 1; i<= n; i++)
    {
        scanf("%d", A+i);
        B[i] = B[i-1] + A[i];
    }
    for(int i = 1; i<= n; i++) dp[1][i] = 0;
    for(int i = 2; i<= k; i++) solve(i, 1, n, 1, n);
    printf("%lld\n", dp[k%2][n]);
    vector<int> cut;
    int remk = k, remn = n;
    while(remk>0 && remn>= 0)
    {
        if(opt[remk][remn]) cut.pb(opt[remk][remn]-1);
        else break;
        remn = opt[remk][remn]-1;
        remk--;
    }
    reverse(cut.begin(), cut.end());
    for(auto x : cut) printf("%d ", x);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:46:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, k; scanf("%d %d", &n, &k);
                                     ^
sequence.cpp:50:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
                         ^

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