oj.uz

Submission #1079437

# Submission time Handle Problem Language Result Execution time Memory
1079437 2024-08-28T14:39:33 Z 12345678 Building Bridges (CEOI17_building) C++17
100 / 100
 50 ms 9680 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e5+5, inf=1e18;

ll n, h[nx], w[nx], sm, dp[nx];
bool querymode;

struct line
{
    ll m, c;
    mutable ll p;
    line(ll m=0, ll c=0, ll p=0): m(m), c(c), p(p){}
    bool operator<(const line &o) const {return querymode?p<o.p:m>o.m;}
};

struct convexhulltrick:multiset<line>
{
    ll div(ll a, ll b)
    {
        if ((a%b)==0||((a^b)>0)) return a/b;
        return a/b-1;
    }
    bool isect(iterator x, iterator y)
    {
        if (y==end()) return x->p=inf, 0;
        if (x->m==y->m) x->p=(x->c<=y->c)?inf:-inf;
        else x->p=div(y->c-x->c, x->m-y->m);
        return x->p>=y->p;
    }
    void add(line l)
    {
        auto x=insert(l), y=next(x);
        while (isect(x, y)) y=erase(y);
        while ((y=x)!=begin()&&isect(--x, y)) isect(x, erase(y));
        while ((y=x)!=begin()&&isect(--x, y)) isect(x, erase(y));
    }
    ll query(ll x)
    {
        querymode=1;
        auto itr=lower_bound(line(0, 0, x));
        querymode=0;
        return itr->m*x+itr->c;
    }
} c;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=1; i<=n; i++) cin>>w[i], sm+=w[i];
    dp[1]=-w[1];
    c.add(line(-2*h[1], dp[1]+h[1]*h[1]));
    for (int i=2; i<=n; i++)
    {
        dp[i]=c.query(h[i])+h[i]*h[i]-w[i];
        c.add(line(-2*h[i], dp[i]+h[i]*h[i]));
        //cout<<"debug "<<i<<' '<<dp[i]<<'\n';
    }
    cout<<sm+dp[n];
}

/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3676 KB Output is correct
2 Correct 30 ms 3760 KB Output is correct
3 Correct 29 ms 3672 KB Output is correct
4 Correct 28 ms 3512 KB Output is correct
5 Correct 27 ms 4700 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 32 ms 3676 KB Output is correct
7 Correct 30 ms 3760 KB Output is correct
8 Correct 29 ms 3672 KB Output is correct
9 Correct 28 ms 3512 KB Output is correct
10 Correct 27 ms 4700 KB Output is correct
11 Correct 29 ms 3928 KB Output is correct
12 Correct 30 ms 3652 KB Output is correct
13 Correct 21 ms 3676 KB Output is correct
14 Correct 29 ms 4044 KB Output is correct
15 Correct 50 ms 9680 KB Output is correct
16 Correct 27 ms 4696 KB Output is correct
17 Correct 13 ms 3672 KB Output is correct
18 Correct 14 ms 3672 KB Output is correct