Submission #403015

#	Time	Username	Problem	Language	Result	Execution time	Memory
403015		radaiosm7	Split the sequence (APIO14_sequence)	C++98	100 / 100	1504 ms	81404 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
int n, k, i, par;
long long pref[100005];
long long dp[2][100005];
int spl[210][100005];

void compute(int l, int r, int optl, int optr) {
  if (l>r) return;
  int mid = (l+r)/2;
  pair<long long, int> ans = make_pair(-1LL, -1);

  for (int j=optl; j <= optr && j < mid; ++j) {
    ans = max(ans, make_pair(dp[!(i&1)][j]+(pref[j]*(pref[mid]-pref[j])), j));
  }

  dp[i&1][mid] = ans.first;
  spl[i][mid] = ans.second;
  compute(l, mid-1, optl, ans.second);
  compute(mid+1, r, ans.second, optr);
}

int main() {
  scanf("%d%d", &n, &k);
  pref[0] = 0LL;
  fill(dp[0], dp[0]+n+5, 0LL);
  fill(dp[1], dp[1]+n+5, 0LL);

  for (i=1; i <= n; ++i) {
    scanf("%lld", &pref[i]);
    pref[i] += pref[i-1];
  }

  for (i=1; i <= k; ++i) {
    compute(1, n, 1, n);
  }

  printf("%lld\n", dp[k&1][n]);
  par = n;
  for (i=k; i > 0; --i) {
    par = spl[i][par];
    printf("%d%c", par, (i==1)?('\n'):(' '));
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%lld", &pref[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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