Submission #23164

#	Time	Username	Problem	Language	Result	Execution time	Memory
23164		ruhanhabib39	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1844 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long Long;

const int MAXN = 1e5;
const int MAXK = 200;

int N, K;
Long A[MAXN + 10], S[MAXN + 10];

Long dp[MAXK + 10][MAXN + 10];
int pos[MAXK + 10][MAXN + 10];

void calc_dp() {
   for(int k = 1; k <= K; k++) {
      for(int i = k; i <= N; i++) {
         dp[k][i] = 0;
         for(int j = max(1, k-1); j < i; j++) {
            if(S[j]*S[i]-S[j]*S[j]+dp[k-1][j] >= dp[k][i]) {
               dp[k][i] = S[j]*S[i] - S[j]*S[j] + dp[k-1][j];
               pos[k][i] = j;
            }
         }
      }
   }
}

int main() {
   scanf("%d%d", &N, &K);
   S[0] = 0;
   for(int i = 1; i <= N; i++) {
      scanf("%lld", &A[i]);
      S[i] = A[i] + S[i-1];
   }
   calc_dp();
   printf("%lld\n", dp[K][N]);
   int i = N, k = K;
   while(k > 0) {
      i = pos[k][i];
      printf("%d ", i);
      k--;
   }
   printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:30: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:33:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &A[i]);
                           ^

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