Submission #1195597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195597		meisgood	Split the sequence (APIO14_sequence)	C++20	100 / 100	706 ms	81788 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define aaa 100003
// #define aaa 1003
int arr[aaa] ;
int dp[2][aaa] ;
signed lst[203][100003] ;
int ps[aaa] ;
int n,k ;
void dc(int x,int l,int r,int ql,int qr){
  int md=(l+r)/2 ;
  int i,j ;
  for (i = ql ; i <= min(md-1,qr) ; i ++){
    dp[(x)%2][md]=max(dp[(x)%2][md],dp[(x+1)%2][i]+(ps[n]-ps[md])*(ps[md]-ps[i])) ;
  }
  for (i = ql ; i <= qr ; i ++){
    if (dp[(x)%2][md]==dp[(x+1)%2][i]+(ps[n]-ps[md])*(ps[md]-ps[i])){
      lst[x][md]=i ;
      break ;
    }
  }
  if (l==r) return ;
  if (md-1>=l) dc(x,l,md-1,ql,i) ;
  if (md+1<=r) dc(x,md+1,r,i,qr) ;
}
signed main() {
  int i,j ;
  cin >> n >> k ;
  for (i = 1 ; i <= n ; i ++) cin >> arr[i],ps[i]=ps[i-1]+arr[i] ;
  // for (i = 0 ; i < 203 ; i ++) for (j = 0 ; j < 100003 ; j ++) dp[i][j]=-LLONG_MAX/2 ;
  for (j = 0 ; j < aaa ; j ++) dp[0][j]=-LLONG_MAX/2 ;
  dp[0][0]=0 ;
  for (i = 1 ; i <= k ; i ++){
    for (j = 0 ; j < aaa ; j ++) dp[i%2][j]=-LLONG_MAX/2 ;
    dc(i,1,n,0,n) ;
  }
  int mx=0 ;
  for (i = 0 ; i <= n ; i ++) mx=max(mx,dp[k%2][i]) ;
  cout << mx << endl ;
  for (i = 0 ; i <= n ; i ++){
    if (mx==dp[k%2][i]){
      vector <int> v ;
      int a=i,b=k ;
      while (b!=0){
        v.push_back(a) ;
        a=lst[b][a] ;
        b-- ;
      }
      reverse(v.begin(),v.end()) ;
      for (auto x : v) cout << x << " " ; cout << endl ;
      return 0 ;
    }
  }
  return 0;
}

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