Submission #897525

#	Time	Username	Problem	Language	Result	Execution time	Memory
897525		duckindog	Split the sequence (APIO14_sequence)	C++14	50 / 100	350 ms	16316 KiB

sequence

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

using namespace std;

#define int long long

const int N = 1e3 + 10;
int n, k;
int a[N], d[N];
int f[N][N], trace[N][N];

int dp(int i, int j) {
  if (j > n - i + 1) return -2e9;
  if (j == 1) return 0;
  int &ret = f[i][j];
  if (ret > -1) return ret;
  for (int x = i; x < n; ++x) {
    int val = (d[x] - d[i - 1]) * (d[n] - d[x]) + dp(x + 1, j - 1);
    if (ret < val) {
      ret = val;
      trace[i][j] = x;
    }
  }
  return ret;
}
void tracer(int i, int j) {
  int mid = trace[i][j];
  if (!mid) return;
  cout << mid << ' ';
  tracer(mid + 1, j - 1);
}

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, k + 1) << '\n';
  tracer(1, k + 1);


}

Compilation message (stderr)

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

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