Submission #897726

#	Time	Username	Problem	Language	Result	Execution time	Memory
897726		duckindog	Split the sequence (APIO14_sequence)	C++14	100 / 100	1433 ms	88076 KiB

sequence

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

using namespace std;

using pii = pair<int, int>;
const int N = 1e5 + 10;
int n, k;
long long d[N];
long long f[N][2];
int trace[N][202];

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

  long long get_y(int x) {
    return 1ll * a * x + b;
  }
};

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 || j == 1) 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 >> d[i]; d[i] += d[i - 1];
  }
  memset(f, -1, sizeof f);


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

  for (int j = 1; j <= k + 1; ++j) {
    int it = j & 1;
    for (int i = 0; i <= n; ++i) f[i][it] = -1;

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

      while (convex.size() >= 2 && compare(nline, convex.end()[-1], convex.end()[-2])) convex.pop_back();

      if (convex.size() && convex.end()[-1].a == nline.a) {
        if (convex.end()[-1].b > nline.b) nline = convex.end()[-1];
        convex.pop_back();
      }
      convex.push_back(nline);

      auto &ret = f[i][it];
      int l = 0, r = int(convex.size()) - 2, it = 0;

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

      ret = convex[it].get_y(d[i]) + d[i] * d[n] - d[i] * d[i];
      trace[i][j] = convex[it].id;
    }

  }
  cout << f[n][k + 1 & 1] << '\n';

  tracer(n, k + 1);

}

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid = l + r >> 1;
      |                   ~~^~~
sequence.cpp:85:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   85 |   cout << f[n][k + 1 & 1] << '\n';
      |                ~~^~~
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: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29