Submission #1174894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174894		ZeroCool	Building Bridges (CEOI17_building)	C++20	100 / 100	62 ms	17308 KiB

building

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define ar array
#define all(v) v.begin(), v.end()

using namespace std;





const int N = 5e5 + 20;
const int LOG = 20;
const int INF = 1e12;
const int MOD = 1e9 + 7;

void chmin(int &x,int y){x = min(x, y);};
void chmax(int &x,int y){x = max(x, y);};
void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct LCT{
    
    int n;

    LCT(int _n){
        n = _n;
    }

    struct Line{
        int m, b;

        int operator()(int x){
            return m * x + b;
        }
    } kek{0ll, -INF};

    vector<Line> s = {kek};
    vector<int> L = {0};
    vector<int> R = {0};

    int get(){
        s.push_back(kek);
        L.push_back(0);
        R.push_back(0);
        return s.size() - 1;
    }

    void upd(int k,int tl,int tr, Line l){
       // cout<<k<<' ';
        if(tl == tr){
            if(l(tl) > s[k](tl))s[k] = l;
            return;
        }
        int tm = (tl + tr) / 2;
        if(s[k].m > l.m)swap(s[k], l);
        if(s[k](tm) < l(tm)){
            swap(s[k], l);
            if(!L[k])L[k] = get();
            upd(L[k], tl, tm, l);
        }else{
            if(!R[k])R[k] = get();
            upd(R[k], tm + 1, tr, l);
        }
    }

    int qry(int k,int tl,int tr,int x){
        if(tl == tr)return s[k](x);
        int tm = (tl + tr) / 2;
        if(x <= tm)return max(s[k](x), (L[k] ? qry(L[k], tl, tm, x) : -INF));
        else return max(s[k](x), (R[k] ? qry(R[k], tm + 1, tr, x) : -INF));
    }

    void upd(Line l){
        upd(0, 0, n - 1, l);
    }
    int qry(int x){
        return qry(0, 0, n - 1, x);
    }
};



signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n;
    int A[n], B[n];
    for(int i = 0;i < n;i++)cin>>A[i];
    int sum = 0;
    //cout<<kek(69)<<'\n';
    for(int i = 0;i < n;i++)cin>>B[i], sum += B[i];
    int dp[n];
    dp[0] = -B[0];
    LCT lct(1e9);
    for(int i = 1;i < n;i++){
        lct.upd({2 * A[i - 1], -dp[i - 1] - A[i - 1] * A[i - 1]});
        //cout<<'\n';
        dp[i] = -lct.qry(A[i]) - B[i] + A[i] * A[i];
    }
    cout<<dp[n -1] + sum;
}

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