Submission #41641

#	Time	Username	Problem	Language	Result	Execution time	Memory
41641		funcsr	수열 (APIO14_sequence)	C++14	60 / 100	2047 ms	86280 KiB

sequence

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
//#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define index(xs, xe, y) (int)(lower_bound(xs, xe, y) - xs)
#define _1 first
#define _2 second
#define pb push_back
#define MOD 1000000007
#define INF (1LL<<60)
typedef pair<long long, long long> P;
P rel(long long p, long long q) {
  if (q == 0) {
    exit(0);
  }
  if (q < 0) p = -p, q = -q;
  return P(p, q);
}
inline P x_intersect(P a, P b) { return rel(b._2-a._2, a._1-b._1); }
inline bool ord(P a, P b) {
  // ap/aq < bp/bq
  return (__int128)a._1*b._2 < (__int128)a._2*b._1;
}

struct ConvexHullTrick {
  vector<P> ps;
  int h = 0;
  void add(long long x, long long y) {
    if (!ps.empty() && ps.back()._1 == x) {
      if (ps.back()._2 <= y) return;
      ps.pop_back();
      if (h == ps.size()) h--;
    }
    P c = P(x, y);
    while (ps.size() >= 2) {
      P a = ps[ps.size()-2], b = ps[ps.size()-1];
      if (ord(x_intersect(b, c), x_intersect(a, c)) && ord(x_intersect(a, c), x_intersect(a, b))) break;
      ps.pop_back();
      if (h == ps.size()) h--;
    }
    ps.pb(P(x, y));
  }
  P f(long long a) {
    if (ps.empty()) return P(-1, INF);
    while (h+1 < ps.size()) {
      if (ord(P(a, 1), x_intersect(ps[h], ps[h+1]))) h++;
      else break;
    }
    return P(ps[h]._1, a*ps[h]._1+ps[h]._2);
  }
};

int N, K;
int B[100001];
int pre[100001][202];

signed main() {
  cin >> N >> K;
  K++;
  rep(i, N) cin >> B[i+1];
  rep(i, N) B[i+1] += B[i];
  rep(i, N+1) rep(j, K+1) pre[i][j] = -1;
  ConvexHullTrick cht;
  cht.add(0, 0);
  long long dp = 0;
  rep(k, K) {
    ConvexHullTrick ncht;
    for (int x=1; x<=N; x++) {
      P p = cht.f(-2LL*B[x]);
      dp = 1LL*B[x]*B[x] + p._2;
      pre[x][k+1] = min(index(B, B+N+1, p._1+1)-1, x-1);
      ncht.add(B[x], dp + 1LL*B[x]*B[x]);
    }
    cht.ps.clear();
    cht.ps.shrink_to_fit();
    swap(cht, ncht);
  }
  long long m = (1LL*B[N]*B[N]-dp)/2LL;
  cout << m << "\n";
  int p = pre[N][K], k = K-1;
  vector<int> seq;
  while (k > 0) {
    seq.pb(p);
    p = pre[p][k];
    k--;
  }
  reverse(all(seq));
  for (int x : seq) cout << x << " "; cout << "\n";
  return 0;
}

Compilation message (stderr)

sequence.cpp: In member function 'void ConvexHullTrick::add(long long int, long long int)':
sequence.cpp:39:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (h == ps.size()) h--;
             ^
sequence.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (h == ps.size()) h--;
             ^
sequence.cpp: In member function 'P ConvexHullTrick::f(long long int)':
sequence.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (h+1 < ps.size()) {
                ^

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