Submission #402990

#	Time	Username	Problem	Language	Result	Execution time	Memory
402990		radaiosm7	Split the sequence (APIO14_sequence)	C++98	43 / 100	127 ms	131076 KiB

sequence

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

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);

  for (int j = optl; j < mid && j <= 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;

  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:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld", &pref[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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