Submission #83145

#	Time	Username	Problem	Language	Result	Execution time	Memory
83145		MrTEK	Split the sequence (APIO14_sequence)	C++14	11 / 100	2057 ms	4372 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e3 + 5;
const int M = 205;

int a[N],n,k;

ll pre[N];
pair <ll,ll> dp[N][M];

ll get(int l,int r) {
  return pre[r] - pre[l - 1];
}

pair <ll,ll> f(int x,int rem) {
  auto &res = dp[x][rem];
  if (res.first != -1)
    return res;
  if (x == n + 1)
    return res = {0,0};
  if (rem == 0)
    return res = {0,get(x,n)};
  for (int i = x + 1 ; i <= n ; i++) {
    auto temp = f(i,rem - 1);
    res = max(res,{temp.second * get(x,i - 1) + temp.first,temp.second + get(x,i - 1)});
  }
  return res;
}

void write(int x,int rem) {
  if (x == n + 1 || rem == 0)
    return ;
  for (int i = x + 1 ; i <= n ; i++) {
    auto temp = dp[i][rem - 1];
    if (dp[x][rem].first == temp.second * get(x,i - 1) + temp.first && dp[x][rem].second == temp.second + get(x,i - 1)) {
      cout << i - 1 << " ";
      write(i,rem - 1);
      break;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> k;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
  }
  memset(dp,-1,sizeof dp);
  cout << f(1,k).first << "\n";
  write(1,k);
}

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