제출 #997361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997361		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	29 ms	6072 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5, K = 205;
const ll inf = 1e18;
vector<vector<ll> > dp;
vector<vector<int> > path;
vector<ll> pref(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++)
    {
      if(dp[k - 1][i] == -inf) continue;
      
      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);
  mid++;
  compute(k, mid, 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 = vector<vector<ll> > (k + 1, vector<ll> (n + 1));
  path = vector<vector<int> > (k + 1, vector<int> (n+1));
  
  dp[0][0] = -inf;
  for(int i = 1; i <= k; i++)
    for(int j = 0; j <= n; j++)
      dp[i][j] = -inf;

  n++;
  for(int i = 1; i <= k; i++) {
    int z = 0;
    compute(i, z, n, z, n);
    /*
      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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29