Submission #997339

#	Time	Username	Problem	Language	Result	Execution time	Memory
997339		vjudge1	Split the sequence (APIO14_sequence)	C++17	33 / 100	2069 ms	131072 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5, K = 205;
const ll inf = 1e18;
ll dp[K][N], pref[N], path[K][N];

void compute(int k, int l, int r, int s, int e)
{
  if(r <= l) return;
  
  int mid = (l + r) / 2;
  int bestj = s;
  for(int i = s; i <= min(e, mid - 1); i++)
    {
      ll val = dp[k - 1][i] + (pref[mid] - pref[i]) * pref[i];
      if(val > dp[k][mid])
	dp[k][mid] = val, bestj = i;
    }
  path[k][mid] = bestj;
  compute(k, l, mid, s, bestj);
  compute(k, mid + 1, r, bestj, e);
}

int main()
{
  int n, k;
  cin >> n >> k;
  pref[0] = 0;
  for(int i = 1; i <= n; i ++)
    {
      int x; cin >> x;
      pref[i] = pref[i - 1] + x;
    }
  dp[0][0] = -inf;
  for(int i = 1; i <= k; i++)
    for(int j = 0; j <= n; j++)
      dp[i][j] = -inf;

  for(int i = 1; i <= k; i++) {
    // compute(i, 0, n+1, 0, n+1);
    for(int j = 0; j <= n; j++)
      for(int l = 0; l < j; l++)
	if(dp[i - 1][l] != -inf)
	  {
	    ll val = dp[i - 1][l] + pref[l] * (pref[j] - pref[l]);
	    if(val >= dp[i][j])
	      dp[i][j] = val, path[i][j] = l;
	  }
  }
  
  cout << dp[k][n] << endl;

  int cur = n;
  vector<int> ans = {};
  int j = k;
  while(j--)
    {
      cur = path[j + 1][cur];
      ans.push_back(cur);
    }
  reverse(ans.begin(), ans.end());
  for(int i : ans)
    cout << i << ' ';
  cout << endl;
  return 0;
}

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