Submission #402953

#	Time	Username	Problem	Language	Result	Execution time	Memory
402953		radaiosm7	Split the sequence (APIO14_sequence)	C++98	0 / 100	1857 ms	33932 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;

  if (i > mid-1) {
    dp[mid][i].first = -999999999LL;
  }

  pair<long long, int> ans = make_pair(0LL, -1);

  for (int j = optl; 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);
}

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

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

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

  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) {
    if (dp[par][i].second == -1) {
      printf("\n");
      break;
    }
    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:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%lld", &pref[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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