Submission #83148

#	Time	Username	Problem	Language	Result	Execution time	Memory
83148		MrTEK	Split the sequence (APIO14_sequence)	C++14	0 / 100	3 ms	876 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e3 + 5;
const int M = 205;

int a[N],n,k;

ll pre[N],dp[N][2];

ll get(int l,int r) {
  return pre[r] - pre[l - 1];
}

void f(int l,int r,int optl,int optr) {
  if (l > r || optl > optr)
    return;
  int mid = (l + r) / 2;
  if (optl == optr)
    dp[mid][0] = optl;
  else {
    for (int i = min(mid + 1,optl) ; i <= optr ; i++)
      dp[mid][0] = max(dp[mid][0],dp[i][1] + get(mid,i - 1) * get(i,n));
  }
  f(l,mid - 1,optl,dp[mid][0]);
  f(mid + 1,r,dp[mid][0],optr);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> k;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 0 ; i <= k ; i++) {
    for (int j = 1 ; j <= n ; j++) {
      dp[j][1] = dp[j][0];
      dp[j][0] = 0;
    }
    f(1,n,1,n);
  }
  cout << dp[1][0] << "\n";
}

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