Submission #1173092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173092		ZeroCool	Building Bridges (CEOI17_building)	C++20	60 / 100	48 ms	10168 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 = 1e5 + 20;
const int LOG = 30;
const int INF = 1e17;

struct Koce{
    int m, b;

    int operator()(int x){
        return m * x + b;
    }

};

Koce inf{(int)-1e12, (int)-1e17};

vector<Koce> s = {inf};
vector<int> le = {0};
vector<int> ri = {0};

int L(int x){
    if(le[x])return le[x];
    le[x] = s.size();
    s.push_back(inf);
    le.push_back(0);
    ri.push_back(0);
    return le[x];
}

int R(int x){
    if(ri[x])return ri[x];
    ri[x] = s.size();
    s.push_back(inf);
    le.push_back(0);
    ri.push_back(0);
    return ri[x];
}

void upd(int k,int tl,int tr, Koce l){
    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);
        upd(L(k), tl, tm, l);
    }else 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), (le[k] ? qry(le[k], tl, tm, x) : -INF));
    else return max(s[k](x), (ri[k] ? qry(ri[k], tm + 1, tr, x) : -INF));
}

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;
    for(int i = 0;i < n;i++)cin>>B[i], sum += B[i];
    int dp[n];
    dp[0] = -B[0];
    for(int i = 1;i < n;i++){
        upd(0, 0, N - 1, {2 * A[i - 1], -dp[i - 1] - A[i - 1] * A[i - 1]});
        dp[i] = -qry(0, 0, N - 1, A[i]) - B[i] + A[i] * A[i];
    }
    cout<<dp[n -1] + sum;
}

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