Submission #897773

#	Time	Username	Problem	Language	Result	Execution time	Memory
897773		duckindog	Split the sequence (APIO14_sequence)	C++14	100 / 100	808 ms	88084 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;
  }
  bool operator == (line x) {
    return (x.a == a && x.b == b && x.id == id);
  }
};

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 (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 now = j & 1;
    for (int i = 0; i <= n; ++i) f[i][now] = -1;

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

      bool bel = 0;
      if (convex.size()) {
        line gate = convex[0];
        while (convex.size() >= 2 && compare(nline, convex.end()[-1], convex.end()[-2])) {
          if (convex.back() == gate) bel = 1; it -= bel;
          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(); it -= bel;
      }
      convex.push_back(nline);

      auto &ret = f[i][now];
      while (it < convex.size() - 1 && translator(convex[it], convex[it + 1]) < d[i]) ++it;

      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:71:11: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   71 |           if (convex.back() == gate) bel = 1; it -= bel;
      |           ^~
sequence.cpp:71:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   71 |           if (convex.back() == gate) bel = 1; it -= bel;
      |                                               ^~
sequence.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |       while (it < convex.size() - 1 && translator(convex[it], convex[it + 1]) < d[i]) ++it;
      |              ~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp:92:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   92 |   cout << f[n][k + 1 & 1] << '\n';
      |                ~~^~~
sequence.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     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