Submission #1113082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113082		available3124	Building Bridges (CEOI17_building)	C++14	100 / 100	87 ms	11336 KiB

building

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define int long long

const int maxn = 2e5;

struct convex_hull {

  struct Line {
    bool type;
    double x;
    int m, c;

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

  set<Line> cht;
  bool has_prev(set<Line>::iterator t) {
    return t != cht.begin();
  }
  bool has_next(set<Line>::iterator t) {
    return t != cht.end() && next(t) != cht.end();
  }
  double interect(set<Line>::iterator l1, set<Line>::iterator l2) {
    return (double)(l1->c - l2->c) / (l2->m - l1->m);
  }

  void calc_x(set<Line>::iterator t) {
    if (has_prev(t)) {
      Line l = *t;
      l.x = interect(prev(t), t);
      cht.insert(cht.erase(t), l);
    }
  }

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

  void add_line(ll m, ll c) {
    set<Line>::iterator it;

    it = cht.lower_bound({0, 0, m, c});
    if (it != cht.end() && it->m == m) {
      if (it->c <= c) {
        return;
      }
      cht.erase(it);
    }

    it = cht.insert({0, 0, m, c}).first;
    if (bad(it)) {
      cht.erase(it);
    } else {
      while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
      while (has_next(it) && bad(next(it))) cht.erase(next(it));

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


  int query(int h) {
    Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
    return l.m * h + l.c;
  }
};

struct Rect {
  int x, y;

  const bool operator<(const Rect &r) {
    return x < r.x || (x == r.x && y > r.y);
  }
};


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

  int n, tot = 0;

  cin >> n;
  vector<int> h(n + 1);

  for (int i = 1; i <= n; i++) cin >> h[i];

  vector<int> w(n + 1);
  vector<int> dp(n + 1);
  for (int i = 1; i <= n; i++) {

    cin >> w[i];

    tot += w[i];

  }


  dp[1] = -w[1];

  convex_hull 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];

  return 0;
}

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