제출 #1360833

#제출 시각아이디문제언어결과실행 시간메모리
1360833Born_To_LaughBuilding Bridges (CEOI17_building)C++17
100 / 100
31 ms8848 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e18 + 7;
#define int ll
struct linecontainer
{
    struct line{
        ll a, b;
        mutable ll p;
        bool operator < (const line& o) const {
            if(o.a == INF && o.b == INF) return p < o.p;
            return a > o.a;
        }
    };
    multiset<line> lc;
    ll div(ll a, ll b){
        return (a / b) - ((a ^ b) < 0 && a % b);
    }
    bool phe(multiset<line>::iterator x, multiset<line>::iterator y){
        if(y == lc.end()){
            x->p = INF;
            return 0;
        }
        if(x->a == y->a){
            if(x->b <= y->b) x->p = INF;
            else x->p = -INF;
            return x->p >= y->p;
        }
        x->p = div(x->b - y->b, y->a - x->a);
        return x->p >= y->p;
    }
    void add(ll a, ll b){
        auto x = lc.insert({a, b, 0});
        auto y = next(x);
        while(phe(x, y)) y = lc.erase(y);
        if((y = x) != lc.begin() && phe(--x, y))
            phe(x, y = lc.erase(y));
        while((y = x) != lc.begin() && (--x)->p >= y->p)
            phe(x, y = lc.erase(y));
    }
    ll qr(ll x){
        assert(!lc.empty());
        line l = *lc.lower_bound({INF, INF, x});
        return l.a * x + l.b;
    }
};
const int maxn = 1e6 + 10;
int n, h[maxn];
ll p[maxn], dp[maxn];
linecontainer lc;
void solve(){
    cin >> n;
    for(int i=1; i<=n; ++i) cin >> h[i];
    for(int i=1; i<=n; ++i){
        ll x;cin >> x;
        p[i] = p[i - 1] + x;
    }
    lc.add(h[1] * -2, h[1] * h[1] - p[1]);
    for(int i=2; i<=n; ++i){
        dp[i] = (h[i] * h[i] + p[i - 1]) + lc.qr(h[i]);
        lc.add(h[i] * -2, h[i] * h[i] - p[i] + dp[i]);
    }
    cout << dp[n] << '\n';
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…