oj.uz

Submission #540869

# Submission time Handle Problem Language Result Execution time Memory
540869 2022-03-21T21:35:13 Z Deepesson Building Bridges (CEOI17_building) C++17
100 / 100
 112 ms 7980 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3888 KB Output is correct
2 Correct 112 ms 3968 KB Output is correct
3 Correct 87 ms 3888 KB Output is correct
4 Correct 76 ms 3676 KB Output is correct
5 Correct 70 ms 6200 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 88 ms 3888 KB Output is correct
7 Correct 112 ms 3968 KB Output is correct
8 Correct 87 ms 3888 KB Output is correct
9 Correct 76 ms 3676 KB Output is correct
10 Correct 70 ms 6200 KB Output is correct
11 Correct 93 ms 4412 KB Output is correct
12 Correct 96 ms 4660 KB Output is correct
13 Correct 85 ms 3772 KB Output is correct
14 Correct 92 ms 4660 KB Output is correct
15 Correct 73 ms 7980 KB Output is correct
16 Correct 79 ms 6204 KB Output is correct
17 Correct 62 ms 3632 KB Output is correct
18 Correct 57 ms 3720 KB Output is correct