Submission #29742

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

sequence

#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

int N, K;
int A[100001];
long long P[100001];
long long dp[10002][202];
int nxt[10002][202];

int main() {
  scanf("%d %d", &N, &K);
  for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
  for(int i = 1; i <= N; i++) P[i] = P[i - 1] + A[i];

  dp[0][1] = LLONG_MIN/2;
  for(int j = 2; j <= K + 1; j++) {
    dp[0][j] = LLONG_MIN/2;
    for(int i = 1; i <= N; i++) {
      dp[i][j] = LLONG_MIN/2;
      for(int k = 1; k <= i; k++) {
        long long curr = (P[i] - P[k - 1]) * (P[k - 1]) + dp[k - 1][j - 1];
        if(curr > dp[i][j]) {
          dp[i][j] = curr;
          nxt[i][j] = k;
        }
      }
    }
  }

  printf("%lld\n", dp[N][K + 1]);

  int i = N, j = K + 1;
  while(j > 1) {
    printf("%d ", nxt[i][j] - 1);
    i = nxt[i][j] - 1;
    j--;
  }
  printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:14:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &K);
                         ^
sequence.cpp:15:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= N; i++) scanf("%d", &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