Submission #992381

#	Time	Username	Problem	Language	Result	Execution time	Memory
992381		four_specks	Building Bridges (CEOI17_building)	C++17	100 / 100	45 ms	8948 KiB

building

#include <bits/stdc++.h>

using namespace std;

long fl_div(long x, long y) {
  return x / y - ((x ^ y) < 0 && x % y);
}

struct LineContainer {
  struct Line {
    long m, c;
    mutable long p;

    bool operator<(const Line &line) const {
      return m < line.m || (m == line.m && c < line.c);
    }

    bool operator<(long x) const {
      return p < x;
    }
  };

  static constexpr long inf = LONG_MAX;

  using SetType = set<Line, less<>>;

  SetType lines;

  bool isect(SetType::iterator it) {
    if (next(it) == lines.end()) {
      it->p = inf;
      return false;
    }
    if (it->m == next(it)->m) {
      it->p = -inf;
    } else {
      it->p = fl_div(next(it)->c - it->c, it->m - next(it)->m);
    }
    return it->p >= next(it)->p;
  }

  void add(long m, long c) {
    auto it = lines.insert({m, c}).first;
    while (isect(it)) {
      lines.erase(next(it));
    }
    if (it != lines.begin() && isect(--it)) {
      lines.erase(next(it));
      isect(it);
    }
    while (it != lines.begin() && isect(--it)) {
      lines.erase(next(it));
      isect(it);
    }
  }

  long query(long x) {
    auto it = lines.lower_bound(x);
    return it->m * x + it->c;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<long> a(n), b(n);
  for (long &x : a) {
    cin >> x;
  }
  for (long &x : b) {
    cin >> x;
  }
  long ans = 0;
  for (long &x : b) {
    ans += x;
    x = -x;
  }
  LineContainer lc;
  auto add = [&](long m, long c) -> void {
    lc.add(-m, -c);
  };
  auto query = [&](long x) -> long {
    return -lc.query(x);
  };
  add(-2 * a[0], a[0] * a[0] + b[0]);
  for (int i = 1; i < n - 1; i++) {
    long cost = query(a[i]) + a[i] * a[i] + b[i];
    add(-2 * a[i], a[i] * a[i] + cost);
  }
  {
    long cost = query(a[n - 1]) + a[n - 1] * a[n - 1] + b[n - 1];
    ans += cost;
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

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