Submission #1208029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208029		KindaGoodGames	Building Bridges (CEOI17_building)	C++20	100 / 100	75 ms	15016 KiB

building

#include<bits/stdc++.h>

#define ll long long
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
using namespace std;

ll INF =numeric_limits<ll>::max()/2;

int eval(pii f, int x){
    return (f.first*x) + f.second;
}

struct Node{
    int l, r;
    pii f = {0,INF};
    int left = -1, right = -1; 
};

vector<Node> S;

struct LiChaoTree{
    int offset = 0;
    int len = 1;
    int root = -1;
    LiChaoTree(int n, int offset = 0){
        this->offset = offset;
        while(len < n){
            len <<= 1;
        }

        root = S.size();
        S.push_back(Node{0,len});
    }  

    int query(int p, int i = -1){
        if(i == -1) i = root;
        int mid = (S[i].l + S[i].r)/2;
        mid -= offset;

        int mi = eval(S[i].f, p);
        if(p < mid && S[i].left != -1) {
            mi = min(mi, query(p,S[i].left));
        }else if(S[i].right != -1){
            mi = min(mi, query(p,S[i].right));
        }

        return mi;
    }

    void add(pii f, int i = -1){
        if(i == -1) i = root;
        if(f.second == INF) return;
        if(S[i].r-S[i].l == 1) return;
        
        int m = (S[i].l + S[i].r)/2;
        m -= offset;
        bool lef = eval(f, S[i].l) < eval(S[i].f, S[i].l);
        bool mid = eval(f, m) < eval(S[i].f, m);

        if(mid){
            swap(f,S[i].f);
        }

        if(lef != mid){
            if(S[i].left == -1){
                S[i].left = S.size();
                S.push_back(Node{S[i].l,m});
            }
            add(f,S[i].left);
        }else{
            if(S[i].right == -1){
                S[i].right = S.size();
                S.push_back(Node{m,S[i].r});
            }
            add(f,S[i].right);
        }
    }
};

int32_t main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> cost(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> cost[i];
        sum += cost[i];
    }

    vector<int> dp(n);
    dp[0] = sum-cost[0];

    LiChaoTree seg(2e9);
    seg.add({-2*arr[0], dp[0] + (arr[0]*arr[0])});
    for(int i= 1; i < n; i++){
        dp[i] =  seg.query(arr[i]) - cost[i] + (arr[i]*arr[i]);

        seg.add({-2*arr[i], dp[i] + (arr[i]*arr[i])});
    }
    
    cout << dp[n-1] << endl;
}

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