Submission #23454

#	Time	Username	Problem	Language	Result	Execution time	Memory
23454		rubabredwan	Split the sequence (APIO14_sequence)	C++14	50 / 100	323 ms	3644 KiB

sequence

/* Bismillahir Rahmanir Rahim */

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
const int M = 205;

long long dp[N][M], A[N], sum[N];
int n, k;

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%lld", &A[i]);
        sum[i] = sum[i-1] + A[i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++){
            for(int div=i-1;div>=1;div--){
                long long add = sum[div] * (sum[i] - sum[div]);
                dp[i][j] = max(dp[i][j], add + dp[div][j-1]);
            }
        }
    }
    cout << dp[n][k] << endl;
    while(k){
        for(int div = n-1;div >= 1;div--){
            long long add = sum[div] * (sum[n] - sum[div]);
            if(dp[div][k-1] + add == dp[n][k]){
                cout << div << ' ';
                n = div;
                break;
            }
        }
        k--;
    }
    cout << endl;
	return 0;
}

Compilation message (stderr)

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

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