Submission #1186362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186362		dombly	Split the sequence (APIO14_sequence)	C++20	0 / 100	1 ms	324 KiB

sequence

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

const int inf = 1e16;

const int K = 205;

int dp[N][K], pref[N], a[N], n, pos[N][K], k;

void Solve(int l, int r, int low, int high, int x) {
  if(l > r) return;
  int mid = l + r >> 1;
  int opt = low, rez = dp[low - 1][x - 1] + pref[low - 1] * (pref[mid] - pref[low - 1]);
  for(int i = low + 1; i <= min(mid, high); i++) {
    if(rez < dp[i - 1][x - 1] + (pref[mid] - pref[i - 1]) * pref[i - 1]) {
      rez = dp[i - 1][x - 1] + (pref[mid] - pref[i - 1]) * pref[i - 1];
      opt = i;
    }
  }
  pos[mid][x] = opt;
  dp[mid][x] = rez;
  Solve(l, mid - 1, low, opt, x);
  Solve(mid + 1, r, opt, high, x);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> k;
  k++;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    pref[i] = pref[i - 1] + a[i];
    dp[i][0] = -inf;
  }
  for(int i = 1; i <= k; i++) Solve(1, n, 1, n, i);
  cout << dp[n][k] << "\n";
  vector<int> ans;
  int index = n, kk = k;
  while(index > 0) {
    if(index != n) ans.push_back(index);
    kk--;
    index = pos[index][kk];
  }
  reverse(ans.begin(), ans.end());
  for(int i : ans) cout << 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