oj.uz

Submission #291176

# Submission time Handle Problem Language Result Execution time Memory
291176 2020-09-04T20:17:33 Z Bench0310 Building Bridges (CEOI17_building) C++17
100 / 100
 82 ms 9848 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf=(1ll<<60);

struct line
{
    ll k,n;
    mutable ll r;
    line(ll a,ll b,ll c){k=a;n=b;r=c;}
    bool operator<(const line &o)const{return k>o.k;}
    bool operator<(const ll &o)const{return r<o;}
};

struct cht
{
    set<line,less<>> s;
    ld intersect(line a,line b){return (((ld)b.n-a.n)/(a.k-b.k));}
    void upd(set<line>::iterator it,ll nr){it->r=nr;}
    void add(ll k,ll n)
    {
        line now(k,n,0);
        auto it=s.lower_bound(now);
        if(it!=s.end()&&it->k==k)
        {
            if(it->n>n) it=s.erase(it);
            else return;
        }
        if(it!=s.end()&&it!=s.begin()&&intersect(*prev(it),now)>intersect(now,*it)) return;
        s.insert(now);
        while(it!=s.end()&&next(it)!=s.end()&&intersect(now,*it)>intersect(*it,*next(it))) it=s.erase(it);
        it--;
        while(it!=s.begin()&&prev(it)!=s.begin()&&intersect(now,*prev(it))<intersect(*prev(it),*prev(prev(it)))) s.erase(prev(it));
        if(it!=s.begin()) upd(prev(it),floor(intersect(*prev(it),*it)));
        if(next(it)!=s.end()) upd(it,floor(intersect(*it,*next(it))));
        else upd(it,inf);
    }
    ll query(ll a)
    {
        line best=*s.lower_bound(a);
        return (best.k*a+best.n);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> h(n+1,0);
    for(int i=1;i<=n;i++) cin >> h[i];
    vector<ll> w(n+1,0);
    for(int i=1;i<=n;i++) cin >> w[i];
    vector<ll> sum(n+1,0);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
    cht c;
    c.add(-2*h[1],h[1]*h[1]-w[1]);
    for(int i=2;i<=n;i++)
    {
        ll dp=h[i]*h[i]+sum[i-1]+c.query(h[i]);
        c.add(-2*h[i],dp+h[i]*h[i]-sum[i]);
        if(i==n) cout << dp << "\n";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3736 KB Output is correct
2 Correct 70 ms 3704 KB Output is correct
3 Correct 69 ms 3832 KB Output is correct
4 Correct 67 ms 3584 KB Output is correct
5 Correct 59 ms 4864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 82 ms 3736 KB Output is correct
7 Correct 70 ms 3704 KB Output is correct
8 Correct 69 ms 3832 KB Output is correct
9 Correct 67 ms 3584 KB Output is correct
10 Correct 59 ms 4864 KB Output is correct
11 Correct 63 ms 3584 KB Output is correct
12 Correct 75 ms 3672 KB Output is correct
13 Correct 46 ms 3576 KB Output is correct
14 Correct 69 ms 3704 KB Output is correct
15 Correct 76 ms 9848 KB Output is correct
16 Correct 70 ms 4856 KB Output is correct
17 Correct 20 ms 3584 KB Output is correct
18 Correct 26 ms 3576 KB Output is correct