Submission #600266

#	Time	Username	Problem	Language	Result	Execution time	Memory
600266		Shin	Building Bridges (CEOI17_building)	C++14	100 / 100	100 ms	10036 KiB

building

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}


struct line_t {
  bool t;
  double in;
  int a; long long b;
  line_t(bool _t = 0, double _in = 0, int _m = 0, long long _c = 0) : t(_t), in(_in), a(_m), b(_c) {}
  long long f(int x) {
    return 1LL * a * x + b;
  }
  bool operator < (const line_t &oth) const {
    if (t || oth.t) {
      return in < oth.in;
    }
    return a > oth.a;
  }
};

struct ConvexHullTrick {
  set<line_t> lns;
  
  long long cdiv(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }

  double inter(line_t ln1, line_t ln2) {
    return (double) (ln1.b - ln2.b) / (ln2.a - ln1.a);
  }

  bool is_keep(set<line_t>::iterator it) {
    if (it == lns.begin() || next(it) == lns.end()) {
      return true;
    }
    return inter(*prev(it), *it) <= inter(*prev(it), *next(it));
  }

  void upd(set<line_t>::iterator it) {
    if (it == lns.begin()) {
      return;
    }
    line_t tmp = *it;
    tmp.in = inter(*prev(it), *it);
    lns.insert(lns.erase(it), tmp);
  }

  void add(int a, long long b) {
    auto it = lns.lower_bound(line_t(0, 0, a, b));
    if (it != lns.end() && it -> a == a) {
      if (it -> b <= b) {
        return;
      }
      lns.erase(it);
    }
    lns.insert(line_t(0, 0, a, b));
    it = lns.lower_bound(line_t(0, 0, a, b));
    if (!is_keep(it)) {
      lns.erase(it);
      return;
    }
    while (it != lns.begin() && !is_keep(prev(it))) {
      lns.erase(prev(it));
    }
    while (it != lns.end() && next(it) != lns.end() && !is_keep(next(it))) {
      lns.erase(next(it));
    }
    if (it != lns.end() && next(it) != lns.end()) {
      upd(next(it));
    }
    upd(it);
  }

  long long get(int x) {
    assert(lns.size() > 0);
    line_t res = *prev(lns.upper_bound(line_t(1, (double) x, 0, 0)));
    return res.f(x);
  }
} cht;

const int N = 1e5 + 7;
int n;
int a[N];
long long dp[N];
long long pref[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i ++) {
    int x; cin >> x;
    pref[i] = pref[i - 1] + x;
  }
  #define SQR(x) 1LL * (x) * (x)
  for (int i = 2; i <= n; i ++) {
    cht.add(-2 * a[i - 1], dp[i - 1] + SQR(a[i - 1]) - pref[i - 1]);
    dp[i] = cht.get(a[i]) + SQR(a[i]) + pref[i - 1];
  }
  cout << dp[n];
  return 0;
}

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