Submission #897499

#	Time	Username	Problem	Language	Result	Execution time	Memory
897499		duckindog	Split the sequence (APIO14_sequence)	C++14	22 / 100	67 ms	5464 KiB

sequence

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 50 + 10;
int n, k;
int a[N], d[N];
int f[N][N][N];
pair<int, int> trace[N][N][N];
int dp(int l, int r, int i) {
  if (i > r - l + 1) return -2e9;
  if (i == 1) return 0;
  int &ret = f[l][r][i];
  if (ret > -1) return ret;
  for (int mid = 1; mid < r; ++mid) {
    int val = (d[mid] - d[l - 1]) * (d[r] - d[mid]);
    for (int j = 1; j < i; ++j) {
      int value = val + dp(l, mid, j) + dp(mid + 1, r, i - j);
      if (ret < value) {
        ret = value;
        trace[l][r][i] = {mid, j};
      }
    }
  }
  return ret;
}
vector<int> duck;
void tracer(int l, int r, int i) {
  int mid, j; tie(mid, j) = trace[l][r][i];
  if (!mid || !j) return;
  duck.push_back(mid);
  tracer(l, mid, j);
  tracer(mid + 1, r, i - j);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i], d[i] = d[i - 1] + a[i];
  memset(f, -1, sizeof f);
  cout << dp(1, n, k + 1) << '\n';
  tracer(1, n, k + 1);
  sort(duck.begin(), duck.end());
  for (auto x : duck) cout << x << ' ';
}

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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