Submission #1300451

#TimeUsernameProblemLanguageResultExecution timeMemory
1300451ezzzayBuilding Bridges (CEOI17_building)C++17
100 / 100
60 ms7456 KiB
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
int h[N],w[N];
int dp[N];
struct Line {
    long long m, b;               // y = m*x + b
    long long eval(long long x) const { return m*x + b; }
};

struct LiChao {
    struct Node {
        Line ln;
        Node *l, *r;
        Node(Line v): ln(v), l(nullptr), r(nullptr) {}
    };

    Node* root = nullptr;
    long long L, R;     // domain of x

    LiChao(long long left, long long right): L(left), R(right) {}

    Node* add(Node* node, long long l, long long r, Line nw) {
        if(!node) return new Node(nw);

        long long mid = (l + r) >> 1;

        // At mid, keep the better line
        if( node->ln.eval(mid) > nw.eval(mid) )
            swap(node->ln, nw);

        if(l == r) return node;

        if( nw.eval(l) < node->ln.eval(l) )
            node->l = add(node->l, l, mid, nw);
        else if( nw.eval(r) < node->ln.eval(r) )
            node->r = add(node->r, mid+1, r, nw);

        return node;
    }

    void add_line(long long m, long long b) {
        Line ln = {m, b};
        root = add(root, L, R, ln);
    }

    long long query(Node* node, long long l, long long r, long long x) const {
        if(!node) return LLONG_MAX / 4;
        long long res = node->ln.eval(x);
        if(l == r) return res;
        long long mid = (l + r) >> 1;
        if(x <= mid) return min(res, query(node->l, l, mid, x));
        else         return min(res, query(node->r, mid+1, r, x));
    }

    long long query(long long x) const {
        return query(root, L, R, x);
    }
};

signed main(){
    int n;
    cin>>n;
    int k=0;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        k+=w[i];
    }
    dp[1]=h[1]*h[1]-h[n]*h[n];
    for(int i=2;i<=n;i++){
        dp[i]=1e18;
    }
    LiChao cht(0, 1e6);
    cht.add_line(-2*h[1], dp[1]);
    
    for(int i = 2; i <= n; i++){
        long long p = h[i]*h[i]*2 - w[i];
        long long best = cht.query(h[i]);
        dp[i] = best + p;
        cht.add_line(-2*h[i], dp[i]);
    }

    cout<<dp[n]+k-w[1];
}
/*6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...