Submission #34044

#	Time	Username	Problem	Language	Result	Execution time	Memory
34044		wan2000	Split the sequence (APIO14_sequence)	C++14	50 / 100	2000 ms	83816 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100001;
const int K = 201;

int n, k, Tr[K][N];
ll A[N], S[N], F[2][N], res;

bool maxi(ll &x, ll y){
    if(x<y) x = y;
    else return 0;
    return 1;
}

void BackTrack(int x, int d){
    if(d==0) return;
    cout<<x<<' ';
    BackTrack(Tr[d][x],d-1);
}



int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>A[i];
        S[i] = S[i-1]+A[i];
    }
    for(int ii = 1; ii <= k; ii++){
        for(int i = n; i >= 1; i--){
            F[ii%2][i] = 0;
            for(int j = i+1; j <= n; j++){
                if(maxi(F[ii%2][i],F[(ii+1)%2][j]+S[i]*(S[j]-S[i]))){
                    Tr[ii][i] = j;
                }
            }
        }
    }
  	res = -1;
    int s;
    for(int i = 1; i <= n; i++){
        if(maxi(res,F[k%2][i])){
            s = i;
        }
    }
    cout<<res<<'\n';
    BackTrack(s,k);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:46:9: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int s;
         ^

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