Submission #239645

#	Time	Username	Problem	Language	Result	Execution time	Memory
239645		neihcr7j	Split the sequence (APIO14_sequence)	C++14	50 / 100	179 ms	2040 KiB

sequence

#include<bits/stdc++.h>

#define maxn 100005

using namespace std;
typedef long long ll;

int n, k;
ll a[maxn];


namespace sub1234{
  ll dp[maxn][203];

  void trace(int i, int ik) {
    if (ik == 1) return;

    for (int j = i - 1; j > 0; --j)
      if (dp[i][ik] == dp[j][ik - 1] + (a[i] - a[j]) * a[j]) {
        trace(j, ik - 1);
        cout << j << ' ';
        break;
      }
  }

  void run() {
    for (int i = 1; i <= n; ++i)
      for (int ik = 2; ik <= k + 1 && ik <= i; ++ik)
        for (int j = 1; j < i; ++j)
          dp[i][ik] = max(dp[i][ik], dp[j][ik - 1] + (a[i] - a[j]) * a[j]);

    cout << dp[n][k + 1] << '\n';
    trace(n, k + 1);
  }
}

namespace sub56{

  void xuli(int& i, int& j, int& k) {
    int l = j + 1, r = k - 1;

    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (a[k] - a[mid] >= a[mid - 1] - a[i])
        l = mid;
      else
        r = mid - 1;
    }
    j = l;
  }

  void run() {
    vector < int > id(k + 1);
    for (int i = 0; i <= k; ++i)
      id[i] = i;
    id.push_back(n);

    while (1) {
      bool flag = 1;
      for (int i = 0; i < k; ++i)
      if (id[i + 2] - id[i + 1] > 1) {
        ll A = a[id[i + 1]] - a[id[i]], B = a[id[i + 2]] - a[id[i + 1] + 1];
        if (B <= A) continue;
        flag = 0;
        xuli(id[i], id[i + 1], id[i + 2]);
        break;
      }

      if (flag) break;
    }

    ll ans = 0;
    for (int i = 2; i <= k + 1; ++i)
      ans +=  (a[id[i]] - a[id[i - 1]]) * a[id[i - 1]];

    cout << ans << '\n';
    for (int i = 1; i <= k; ++i)
      cout << id[i] << ' ';
  }
}

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> k;

  for (int i = 1; i <= n; ++i)
    cin >> a[i];

  for (int i = 1; i <= n; ++i)
      a[i] += a[i - 1];

  //sub56::run(); return 0;

  if (n <= 1000)
    sub1234::run();
  else
    sub56::run();

  return 0;
}

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