Submission #540869

#	Time	Username	Problem	Language	Result	Execution time	Memory
540869		Deepesson	Building Bridges (CEOI17_building)	C++17	100 / 100	112 ms	7980 KiB

building

#include <bits/stdc++.h>
#define MAX 210000
typedef long long ftype;
typedef std::pair<ftype,ftype> point;

ftype f(point a,  ftype x) {
    return a.first*x + a.second;
}
const long long val = 1LL<<30LL;
const int maxn = 2e5;
const int membros = 35 * maxn;
point mem[membros];
int lefta[membros],righta[membros];
int cur=3;
int alocar(void){
    int x=cur;
    if(x==35*maxn)assert(0);
    cur++;
    mem[x]={0,1LL<<62LL};
    return x;
}
int inicio = alocar();

void add_line(point nw, int v = inicio, long long l = -val, long long r = val) {
    long long m = (l + r) / 2LL;
    bool lef = f(nw, l) < f(mem[v], l);
    bool mid = f(nw, m) < f(mem[v], m);
    if(mid) {
        std::swap(mem[v], nw);
    }
    if(r-l==1) {
        return;
    } else if(lef != mid) {
        if(!lefta[v])lefta[v]=alocar();
        add_line(nw, lefta[v], l, m);
    } else {
        if(!righta[v])righta[v]=alocar();
        add_line(nw,righta[v], m, r);
    }
}
ftype get(int x, int v = inicio, long long l = -val, long long r = val) {
    if(!v)return 1LL<<62LL;
    long long m = (l + r) / 2LL;
    if(r-l==1) {
        return f(mem[v], x);
    } else if(x < m) {
        return std::min(f(mem[v], x), get(x, lefta[v], l, m));
    } else {
        return std::min(f(mem[v], x), get(x, righta[v], m, r));
    }
}
using ll = long long;

int main()
{
    ll N;
    std::cin>>N;
    ll a[N],b[N];
    for(auto&x:a)std::cin>>x;
    for(auto&x:b)std::cin>>x;
    ll p[N];
    {
        ll s=0;
        for(int i=0;i!=N;++i){
            s+=b[i];
            p[i]=s;
        }
    }
    ll resp;
    for(int i=0;i!=N;++i){
        ll custo=0;
        if(i){
            ll ans = get(a[i]);
            custo=ans+(a[i]*a[i])+p[i-1];
        }
        resp=custo;
        add_line({-2LL*a[i],(a[i]*a[i])+custo-p[i]});
    }
    std::cout<<resp<<"\n";
}

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