Submission #1300024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300024		tuncay_pasha	Split the sequence (APIO14_sequence)	C++20	0 / 100	109 ms	1572 KiB

sequence

#include "bits/stdc++.h"

using namespace std;

#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>

const int N = 1e5 + 5;
const int K = 205;

pair<int, vi> dp[K][N];
int a[N];

void solve() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  int cur = 0;
  for (int i = 1; i <= n; ++i) {
    cur += a[i];
  }
  auto check = [&](int idx, int i, int j) -> bool {
    int lo = 0, hi = dp[i][j].second.size() - 1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (dp[i][j].second[mid] == idx) {
        return true;
      }
      else if (dp[i][j].second[mid] < idx) {
        lo = mid + 1;
      }
      else hi = mid - 1;
    }
    return false;
  };
  for (int i = 1; i <= k; ++i) {
    for (int j = 1; j < n; ++j) {
      for (int l = 1; l < n; ++l) {
        if (l == j || check(j, i - 1, l) == true) continue;
        vi odp = dp[i - 1][l].second;
        sort (odp.begin(), odp.end());
        int last = (i == 1 ? 0 : odp.back());
        odp.push_back(j), sort (odp.begin(), odp.end());
        vi divide(n + 1, false);
        for (int &z : odp) {
          divide[z] = true;
        }
        int cur = 0, cost = 1;
        for (int z = last + 1; z <= n; ++z) {
          cur += a[z];
          if (divide[z] == true) {
            cost *= cur;
            cur = 0;
          }
        }
        cost *= cur;
        if (dp[i - 1][l].first + cost <= dp[i][j].first) {
          continue;
        }
        dp[i][j].first = dp[i - 1][l].first + cost, dp[i][j].second = odp;
      }
    }
  }
  int id = 1;
  for (int i = 1; i < n; ++i) {
    if (dp[k][id].first < dp[k][i].first) {
      id = i;
    }
  }
  vi ans = dp[k][id].second;
  cout << dp[k][id].first << '\n';
  for (int &i : ans) {
    cout << i << ' ';
  }
  cout << '\n';
}

signed main() {
  int t = 1;
  // cin >> t;
  for (int cs = 1; cs <= t; ++cs) {
    solve();
  }
  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