제출 #997368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997368		vjudge1	수열 (APIO14_sequence)	C++17	100 / 100	1222 ms	82240 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;
  bool b = k % 2, nb = !b;
  int mid = (l + r) / 2;
  dp[b][mid] = -inf;
  int bestj = s;
  for(int i = s; i <= min(e, mid - 1); i++)
    {
      if(dp[nb][i] == -inf) continue;
      
      ll val = dp[nb][i] + (pref[mid] - pref[i]) * pref[i];
      if(val > dp[b][mid])
	dp[b][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> > (2, vector<ll> (n + 1));
  path = vector<vector<int> > (k + 1, vector<int> (n+1));
  
  dp[0][0] = -inf;
    for(int j = 0; j <= n; j++)
      dp[1][j] = -inf;

  n++;
  for(int i = 1; i <= k; i++) {
      int z = 0;
      compute(i, z, n, z, n);
    }
  n--;
  cout << dp[k % 2][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: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29