Submission #1086382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086382		juicy	Building Bridges (CEOI17_building)	C++17	100 / 100	44 ms	7744 KiB

building

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const long long inf = 1e18;

struct line {
  mutable long long a, b, p;

  bool operator < (line o) const {
    return a < o.a;
  }

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

struct lc : multiset<line, less<>> {
  long long div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b); 
  }

  bool isect(iterator x, iterator y) {
    if (y == end()) {
      return x -> p = inf, 0;
    }
    if (x -> a == y -> a) {
      x -> p = x -> b >= y -> b ? inf : -inf;
    } else {
      x -> p = div(y -> b - x -> b, x -> a - y -> a);
    }
    return x -> p >= y -> p;
  }

  void add(long long a, long long b) {
    auto z = insert({a, b, 0}), y = z++, x = y;
    while (isect(y, z)) {
      z = erase(z);
    }
    if (x != begin() && isect(--x, y)) {
      isect(x, erase(y));
    }
    while ((y = x) != begin() && (--x) -> p >= y -> p) {
      isect(x, erase(y));
    }
  }

  long long qry(long long x) {
    auto l = *lower_bound(x);
    return l.a * x + l.b;
  }
};

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

  int n; cin >> n;
  vector<int> h(n);
  for (int &x : h) {
    cin >> x;
  }
  lc lc;
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    int w; cin >> w;
    long long x = lc.size() ? -lc.qry(h[i]) + (long long) h[i] * h[i] + sum : 0;
    sum += w;
    if (i == n - 1) {
      cout << x;
    } else {
      lc.add(2 * h[i], sum - (long long) h[i] * h[i] - x);
    }
  }
  return 0;
}

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