Submission #1109487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109487		available3124	Building Bridges (CEOI17_building)	C++14	100 / 100	83 ms	11348 KiB

building

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define int long long

const int maxn = 2e5;

struct convex_trick {
  struct Line {
    bool type;
    double x;
    int k, b;

    const bool operator<(const Line &other) const {
      if (type || other.type) {
        return x < other.x;
      }
      return k > other.k;
    }
  };


  double intersection(const set<Line>::iterator &l, const set<Line>::iterator &r) { return (double)(l->b - r->b) / (r->k - l->k); }

  set<Line> lines;

  inline bool has_prev(const set<Line>::iterator &it) { return it != lines.begin(); }
  inline bool has_next(const set<Line>::iterator &it) { return it != lines.end() && next(it) != lines.end(); }


  bool bad(set<Line>::iterator it) {
    if (has_next(it) && next(it)->b <= it->b) return true;
    return (has_prev(it) && has_next(it) && intersection(prev(it), next(it)) <= intersection(prev(it), it));
  }

  void calc_x(const set<Line>::iterator &it) {
    if (has_prev(it)) {
      Line l = *it;
      l.x = intersection(prev(it), it);
      lines.insert(lines.erase(it), l);
    }
  }

  void add_line(int k, int b) {
    set<Line>::iterator it;

    it = lines.lower_bound({0, 0, k, b});
    if (it != lines.end() && it->k == k) {
      if (it->b <= b) return;
      lines.erase(it);
    }
    it = lines.insert({0, 0, k, b}).first;
    if (bad(it)) {
      lines.erase(it);
    } else {
      while (has_prev(it) && bad(prev(it))) lines.erase(prev(it));
      while (has_next(it) && bad(next(it))) lines.erase(next(it));

      if (has_next(it)) calc_x(next(it));
      calc_x(it);
    }
  }

  int query(int x) {
    if (!has_prev(lines.upper_bound({1, (double)x, 0, 0}))) {
      assert(false);
    }
    Line l = *prev(lines.upper_bound({1, (double)x, 0, 0}));
    return l.k * x + l.b;
  }
};

struct Rect {
  int w, h;
  const bool operator<(const Rect &other) const {
    return w < other.w || (w == other.w && h > other.h);
  }
};

void run_test(int test_case) {
  int n;
  cin >> n;
  vector<int> h(n + 1), w(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    tot += w[i];
  }
  vector<int> dp(n + 1);
  dp[1] = -w[1];
  convex_trick cht;
  for (int i = 2; i <= n; i++) {
    cht.add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
    dp[i] = cht.query(h[i]) - w[i] + h[i] * h[i];
  }
  cout << tot + dp[n] << '\n';
}

signed main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int test_cases = 1;
  // cin >> test_cases;

  for (int i = 1; i <= test_cases; i++) {
    run_test(i);
  }

  return 0;
}

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