Submission #35633

#	Time	Username	Problem	Language	Result	Execution time	Memory
35633		szawinis	Building Bridges (CEOI17_building)	C++14	100 / 100	189 ms	13900 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = (1e9)+7, INF = 1e18;
const int MAX = (1e5)+1;

struct line {
  ll m, c;
  mutable function<const line*()> succ;
  ll getVal(ll x) { return m*x + c; }
  bool operator<(const line& rhs) const {
    if(rhs.c != -INF) return m > rhs.m;
    const line* s = succ();
    if(!s) return false;
    return ((double) c - s->c > (double) (s->m - m)*rhs.m);
  }
};

class MinHull : public multiset<line> {
  bool bad(iterator it) {
    auto nxt = next(it);
    if(it == begin()) {
      if(nxt != end()) return nxt->m == it->m && nxt->c <= it->c;
      else return false;
    }
    auto pre = prev(it);
    if(nxt == end()) return pre->m == it->m && pre->c <= it->c;
    line l1 = *pre, l2 = *it, l3 = *nxt;
    return (double) (l3.c-l1.c)*(l1.m-l2.m) <= (double) (l2.c-l1.c)*(l1.m-l3.m);
  }
public:
  void update(ll m, ll c) {
    auto it = insert({m, c});
    it->succ = [=] { return next(it) != end() ? &*next(it) : 0; };
    if(bad(it)) {
      erase(it);
      return;
    }
    while(it != begin() && bad(prev(it))) erase(prev(it));
    while(next(it) != end() && bad(next(it))) erase(next(it));
  }
  ll query(ll x) {
    line l = *lower_bound({x, -INF});
    return l.getVal(x);
  }
} hull;

int n;
ll h[MAX], w[MAX], dp[MAX];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> h[i];
  for(int i = 1; i <= n; i++) {
    cin >> w[i];
    w[i] += w[i-1];
  }
  dp[1] = 0;
  hull.update(-2*h[1], dp[1]+h[1]*h[1] - w[1]);
  for(int i = 2; i <= n; i++) {
    dp[i] = hull.query(h[i]) + h[i]*h[i] + w[i-1];
    hull.update(-2*h[i], dp[i] + h[i]*h[i] - w[i]);
  }
  cout << dp[n];
}

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