Submission #93594

#	Time	Username	Problem	Language	Result	Execution time	Memory
93594		dragonslayerit	Split the sequence (APIO14_sequence)	C++14	50 / 100	2062 ms	6776 KiB

sequence

#include <cstdio>
#include <stdint.h>
#include <algorithm>

int64_t as[100005];

int64_t prefix[100005];
int64_t dp[201][100005];
int64_t from[201][100005];

int main(){
  int64_t N,K;
  scanf("%ld %ld",&N,&K);
  for(int64_t i=1;i<=N;i++){
    scanf("%ld",&as[i]);
    prefix[i]=as[i]+prefix[i-1];
  }
  for(int64_t k=1;k<=K+1;k++){
    for(int64_t i=1;i<=N;i++){
      for(int64_t j=0;j<i;j++){
	int64_t to=dp[k-1][j]+prefix[j]*(prefix[i]-prefix[j]);
	if(dp[k][i]<=to){
	  dp[k][i]=to;
	  from[k][i]=j;
	}
      }
      //printf("dp[%ld][%ld]=%ld\n",k,i,dp[k][i]);
    }
  }
  printf("%ld\n",dp[K][N]);
  for(int64_t k=K;k>0;k--){
    printf("%ld",N=from[k][N]);
    if(k>1) printf(" "); else printf("\n");
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%ld %ld",&N,&K);
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%ld",&as[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