Submission #29701

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

sequence

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

using namespace std;

int N, K;
int A[100000];
long long P[100000];
long long dp[10001][202];
int nxt[10001][202];

long long query(int i, int j) {
  if(i > j) return 0;
  if(i == 0) return P[j];
  return P[j] - P[i - 1];
}

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

  for(int i = 0; i < N; i++) dp[i][0] = LLONG_MIN/2;
  dp[N][0] = 0;

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

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

  int i = 0, 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:20: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:21:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; 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