Submission #1113786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113786		Zero_OP	Building Bridges (CEOI17_building)	C++14	100 / 100	38 ms	14672 KiB

building

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
typedef long long ll;
typedef long double ld;
 
struct Line {
  mutable ll m, b, p;
  bool operator<(const Line& o) const { return m < o.m; }
  bool operator<(ll x) const { return p < x; }
};
 
struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  // Caution : This template solve for finding MAX, so if want to find MIN, NEGATE ALL THE LINE FUNCTION
    const ll inf = LLONG_MAX;
  ll div(ll a, ll b) { // floored division
    return a/b-((a^b)<0&&a%b); }
  bool isect(iterator x, iterator y) {
    if (y==end()) { x->p=inf; return false; }
    if (x->m==y->m) x->p=x->b>y->b?inf:-inf;
    else x->p=div(y->b-x->b, x->m-y->m);
    return x->p>=y->p;
  }
  void add(ll m, ll b) {
    m = -m; b = -b;
    auto z=insert({m, b, 0}), y=z++, x=y;
    while(isect(y, z)) z=erase(z);
    if (x!=begin() && isect(--x, y)) isect(x, y = erase(y));
    while((y = x)!=begin() && (--x)->p>=y->p)
    isect(x, erase(y));
  }
  ll query(ll x) { // max value at x
    assert(!empty());
    auto l=*lower_bound(x);
    return -(l.m*x+l.b);
  }
};
 
int n;
ll dp[N], h[N], w[N];
 
int main(){
    ios_base::sync_with_stdio(0);
    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];
 
    LineContainer cht;
    cht.add(h[1], h[1] * h[1] + dp[1] - w[1]);
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + cht.query(-2 * h[i]);
        cht.add(h[i], h[i] * h[i] + dp[i] - w[i]);
    }
 
    cout << dp[n];
    return 0;
}

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