Submission #897695

#	Time	Username	Problem	Language	Result	Execution time	Memory
897695		duckindog	Split the sequence (APIO14_sequence)	C++14	0 / 100	109 ms	34368 KiB

sequence

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

using namespace std;

#define int long long

using pii = pair<int, int>;
const int N = 1e4 + 10;
int n, k;
int a[N], d[N];
int f[N][210], trace[N][210], re[N];

struct line {
  int a, b, id = 0;
};

double translator(line x, line y) {
  return 1.0 * (x.b - y.b) / (y.a - x.a);
}
bool compare(line a, line b, line c) {
  if (a.a == b.a) return a.b >= b.b;
  double x = translator(a, c), y = translator(b, c);
  return x <= y;
}

void tracer(int i, int j) {
  int mid = trace[i][j];
  if (!mid) return;
  tracer(mid, j - 1);
  cout << mid << ' ';
}


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);


  for (int i = 0; i <= n; ++i) f[i][0] = 0;

  for (int j = 1; j <= k + 1; ++j) {
    vector<line> convex = {{0, 0, 0}};
    for (int i = j; i <= n; ++i) {
      line nline = {d[i - 1], -d[i - 1] * d[n] + f[i - 1][j - 1], i - 1};

      while (convex.size() >= 2) {
        if (compare(nline, convex.end()[-1], convex.end()[-2])) convex.pop_back();
        else break;
      }
      if (convex.end()[-1].a == nline.a) {
        if (convex.end()[-1].b > nline.b) nline = convex.end()[-1];
        convex.pop_back();
      }
      convex.push_back(nline);

      int &ret = f[i][j];
      int l = 0, r = 1ll * convex.size() - 2, it = 0;
      int x = d[i];

      while (l <= r) {
        int mid = l + r >> 1;
        if (translator(convex[mid], convex[mid + 1]) < x) l = it = mid + 1;
        else r = mid - 1;
      }

      int a = convex[it].a, b = convex[it].b, id = convex[it].id;
      int constant = d[i] * d[n] - d[i] * d[i];
      ret = a * x + b + constant;
      trace[i][j] = id;
    }

  }

  cout << f[n][k + 1] << '\n';
  tracer(n, k + 1);



}

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
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.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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