Submission #402984

#	Time	Username	Problem	Language	Result	Execution time	Memory
402984		radaiosm7	Split the sequence (APIO14_sequence)	C++98	22 / 100	1478 ms	34316 KiB

sequence

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

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

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

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

  else {
     com(l, mid-1, optl, optr);
     com(mid+1, r, optl, optr);
  }
}

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

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

  for (i=0; i <= n; ++i) {
    dp[i][0].first = 0LL;
    dp[i][0].second = 0;
  }

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

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

Compilation message (stderr)

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

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