Submission #601554

#	Time	Username	Problem	Language	Result	Execution time	Memory
601554		jjiangly	Split the sequence (APIO14_sequence)	C++14	22 / 100	13 ms	1404 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf LLONG_MAX

const int nxm = int(2e2) + 7;
int n, k, a[nxm];

namespace sub3 {
  void solve() {
    vt<ll> prf = {0};
    for (int i = 0; i < n; ++i) {
      prf.push_back(prf.back() + a[i]);
    }
    ll ans = 0;
    vt<vt<ll>> dp(n + 1, vt<ll> (k + 1, 0));
    vt<vt<int>> prf2(n + 1, vt<int> (k + 1, -1));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int l = 0; l < i; ++l) {
          if (dp[i][j] < dp[l][j - 1] + (prf[i] - prf[l]) * (prf[n] - prf[i])) {
            dp[i][j] = dp[l][j - 1] + (prf[i] - prf[l]) * (prf[n] - prf[i]);
            // i = 3, j = 2, l = 1
            prf2[i][j] = l;
          }
          if (j == k) {
            ans = max(ans, dp[i][j]);
          }
        }
      }
    }
    vt<int> path;
    int cur = 0;
    for (int i = 1; i <= n; ++i) {
      if (dp[i][k] == ans) {
        cur = i;
        break;
      }
    }
    while (k) {
      assert(cur != -1);
      path.push_back(cur);
      cur = prf2[cur][k];
      --k;
    }
    cout << ans << "\n";
    for (int i = siz(path) - 1; i >= 0; --i) {
      assert(path[i] > 0 && path[i] <= n);
      cout << path[i] << " \n"[i == 0];
    }
  }
};

int subtask() {
  if (n <= 200) {
    return 3;
  }
  return 4;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  assert(n < nxm);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  if (subtask() == 3) {
    sub3::solve();
  }

  return 0;
}

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