Submission #121364

#	Time	Username	Problem	Language	Result	Execution time	Memory
121364		IOrtroiii	Split the sequence (APIO14_sequence)	C++14	100 / 100	433 ms	85136 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e18;

struct Line {
   int a; ll b;
   Line(int a = 0, ll b = 0) : a(a), b(b) {}
   ll f(int x) { return (ll) a * x + b; }
};

bool bad(Line x, Line y, Line z) {
   return (ll) (x.b - z.b) * (y.a - x.a) <= (ll) (z.a - x.a) * (x.b - y.b);
}

const int N = 100100;

struct Hull {
   Line ls[N];
   int go[N];
   int h, t;
   void reset() { h = t = 0; }
   void add(Line z, int id) {
      while (h + 1 < t && bad(ls[t - 2], ls[t - 1], z)) {
         t--;
      }
      ls[t] = z;
      go[t++] = id;
   }
   int trace() {
      return go[h];
   }
   ll get(int x) {
      while (h + 1 < t && ls[h].f(x) <= ls[h + 1].f(x)) {
         ++h;
      }
      return ls[h].f(x);
   }
} hull[2];

ll f[2][N];
int a[N];
int go[205][N];
int ans[205];

int main() {
   int n, k;
   scanf("%d %d", &n, &k);
   for (int i = 1; i <= n; ++i) {
      scanf("%d", a + i);
      a[i] += a[i - 1];
   }
   int now = 0, nxt = 1;
   for (int j = 1; j <= k; ++j) {
      hull[nxt].reset();
      for (int i = 1; i <= n; ++i) {
         f[nxt][i] = hull[now].get(a[i]);
         go[j][i] = hull[now].trace();
         hull[now].add(Line(a[i], f[now][i] - (ll) a[i] * a[i]), i);
      }
      swap(now, nxt);
   }
   printf("%lld\n", f[now][n]);
   now = n;
   for (int i = k; i > 0; --i) {
      now = go[i][now];
      ans[i] = now;
   }
   for (int i = 1; i <= k; ++i) {
      printf("%d ", ans[i]);
   }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &k);
    ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:52:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", a + i);
       ~~~~~^~~~~~~~~~~~~

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