oj.uz

Submission #578229

# Submission time Handle Problem Language Result Execution time Memory
578229 2022-06-16T08:49:11 Z andrei_boaca Building Bridges (CEOI17_building) C++14
100 / 100
 92 ms 82872 KB 
#include <bits/stdc++.h>
#define MAXH 1000000
using namespace std;
typedef long long ll;
ll n;
ll h[100005],w[100005];
ll dp[100005];
ll s[100005];
struct func
{
    ll a,b;
};
func arb[5000005];
ll f(func e,ll x)
{
    return e.a*x+e.b;
}
ll intersect(func e, func g)
{
    if(g.a>0)
        return -100;
    return (g.b-e.b)/(e.a-g.a);
}
void update(ll nod,ll st,ll dr, func e)
{
    if(st==dr)
    {
        ll x1=f(arb[nod],st);
        ll x2=f(e,st);
        if(x2<x1)
            arb[nod]=e;
        return;
    }
    ll mij=(st+dr)/2;
    if(arb[nod].a==e.a)
    {
        if(arb[nod].b>e.b)
            arb[nod]=e;
        return;
    }
    func l1=e;
    func l2=arb[nod];
    if(l1.a>l2.a)
        swap(l1,l2);
    ll p=intersect(l1,l2);
    if(p<st)
    {
        arb[nod]=l1;
        return;
    }
    if(p>dr)
    {
        arb[nod]=l2;
        return;
    }
    if(p<=mij)
    {
        arb[nod]=l1;
        update(nod*2,st,mij,l2);
        return;
    }
    if(p>mij)
    {
        arb[nod]=l2;
        update(nod*2+1,mij+1,dr,l1);
        return;
    }
}
ll query(ll nod,ll st,ll dr, ll x)
{
    ll ans=f(arb[nod],x);
    if(st==dr)
        return ans;
    ll mij=(st+dr)/2;
    if(x<=mij)
        ans=min(ans,query(nod*2,st,mij,x));
    else
        ans=min(ans,query(nod*2+1,mij+1,dr,x));
    return ans;
}
int main()
{
    ios_base::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];
        s[i]=s[i-1]+w[i];
    }
    for(int i=1;i<=5*MAXH;i++)
        arb[i]={ll(1e11),ll(1e11)};
    dp[1]=0;
    func e={-2*h[1],dp[1]-s[1]+h[1]*h[1]};
    update(1,0,MAXH,e);
    for(int i=2;i<=n;i++)
    {
        dp[i]=query(1,0,MAXH,h[i])+s[i-1]+h[i]*h[i];
        e={-2*h[i],dp[i]-s[i]+h[i]*h[i]};
        update(1,0,MAXH,e);
    }
    cout<<dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 78484 KB Output is correct
2 Correct 34 ms 78676 KB Output is correct
3 Correct 32 ms 78500 KB Output is correct
4 Correct 33 ms 78540 KB Output is correct
5 Correct 35 ms 78748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 81688 KB Output is correct
2 Correct 85 ms 82656 KB Output is correct
3 Correct 78 ms 82704 KB Output is correct
4 Correct 73 ms 82596 KB Output is correct
5 Correct 69 ms 82568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 78484 KB Output is correct
2 Correct 34 ms 78676 KB Output is correct
3 Correct 32 ms 78500 KB Output is correct
4 Correct 33 ms 78540 KB Output is correct
5 Correct 35 ms 78748 KB Output is correct
6 Correct 76 ms 81688 KB Output is correct
7 Correct 85 ms 82656 KB Output is correct
8 Correct 78 ms 82704 KB Output is correct
9 Correct 73 ms 82596 KB Output is correct
10 Correct 69 ms 82568 KB Output is correct
11 Correct 78 ms 82872 KB Output is correct
12 Correct 82 ms 82616 KB Output is correct
13 Correct 92 ms 82752 KB Output is correct
14 Correct 77 ms 82764 KB Output is correct
15 Correct 74 ms 82536 KB Output is correct
16 Correct 70 ms 82636 KB Output is correct
17 Correct 59 ms 82680 KB Output is correct
18 Correct 57 ms 82744 KB Output is correct