Submission #679893

#	Time	Username	Problem	Language	Result	Execution time	Memory
679893		peijar	Building Bridges (CEOI17_building)	C++17	100 / 100	49 ms	10568 KiB

building

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Line {
  mutable int k, m, p;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(int x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  static const int inf = LLONG_MAX;
  int div(int a, int b) { // floored division
    return a / b - ((a ^ b) < 0 && a % b);
  }
  bool isect(iterator x, iterator y) {
    if (y == end())
      return x->p = inf, 0;
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(int k, int m) {
    k *= -1, m *= -1;
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z))
      z = erase(z);
    if (x != begin() && isect(--x, y))
      isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }
  int query(int x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return -(l.k * x + l.m);
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> h(N), w(N);
  vector<int> pref(N + 1);
  for (int &x : h)
    cin >> x;
  for (int i = 0; i < N; ++i) {
    cin >> w[i];
    pref[i + 1] = pref[i] + w[i];
  }

  dbg(pref);

  LineContainer lc;
  lc.add(-2 * h[0], h[0] * h[0] - pref[1]);
  vector<int> dp(N);
  for (int i = 1; i < N; ++i) {
    int valMin = lc.query(h[i]);
    dbg(i, valMin, h[i]);
    dp[i] = h[i] * h[i] + pref[i] + valMin;
    lc.add(-2 * h[i], h[i] * h[i] + dp[i] - pref[i + 1]);
  }
  cout << dp[N - 1] << endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40