oj.uz

Submission #46981

# Submission time Handle Problem Language Result Execution time Memory
46981 2018-04-25T16:33:04 Z dqhungdl Building Bridges (CEOI17_building) C++17
100 / 100
 119 ms 78036 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t n,a[100005],b[100005],F[100005];
ii tree[4000005];

int64_t f(ii line,int64_t x)
{
    return line.first*x+line.second;
}

void Update(int64_t k,int64_t l,int64_t r,ii line)
{
    int64_t mid=(l+r)/2;
    bool cleft=(f(line,l)<f(tree[k],l));
    bool cmid=(f(line,mid)<f(tree[k],mid));
    if(cmid==true)
        swap(tree[k],line);
    if(r-l==1)
        return;
    if(cleft!=cmid)
        Update(2*k,l,mid,line);
    else
        Update(2*k+1,mid,r,line);
}

int64_t Query(int64_t k,int64_t l,int64_t r,int64_t x)
{
    int64_t mid=(l+r)/2;
    if(r-l==1)
        return f(tree[k],x);
    if(x<=mid)
        return min(Query(2*k,l,mid,x),f(tree[k],x));
    return min(Query(2*k+1,mid,r,x),f(tree[k],x));
}

void Naive()
{
    for(int64_t i=2;i<=n;i++)
    {
        F[i]=1e15;
        for(int64_t j=1;j<i;j++)
            F[i]=min(F[i],F[j]+(a[i]-a[j])*(a[i]-a[j])+b[i-1]-b[j]);
    }
    for(int64_t i=1;i<=n;i++)
        cout<<F[i]<<' ';
    exit(0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n;
    for(int64_t i=1;i<=n;i++)
        cin>>a[i];
    for(int64_t i=1;i<=n;i++)
    {
        cin>>b[i];
        b[i]+=b[i-1];
    }
    //Naive();
    for(int64_t i=1;i<=4e6;i++)
        tree[i]=ii(0,1e15);
    Update(1,0,1e6,ii(-2*a[1],F[1]+a[1]*a[1]-b[1]));
    for(int64_t i=2;i<=n;i++)
    {
        F[i]=Query(1,0,1e6,a[i])+a[i]*a[i]+b[i-1];
        Update(1,0,1e6,ii(-2*a[i],F[i]+a[i]*a[i]-b[i]));
    }
    cout<<F[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 62968 KB Output is correct
2 Correct 47 ms 63080 KB Output is correct
3 Correct 46 ms 63080 KB Output is correct
4 Correct 46 ms 63080 KB Output is correct
5 Correct 45 ms 63104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 65408 KB Output is correct
2 Correct 98 ms 66620 KB Output is correct
3 Correct 96 ms 67476 KB Output is correct
4 Correct 98 ms 68416 KB Output is correct
5 Correct 97 ms 69480 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 62968 KB Output is correct
2 Correct 47 ms 63080 KB Output is correct
3 Correct 46 ms 63080 KB Output is correct
4 Correct 46 ms 63080 KB Output is correct
5 Correct 45 ms 63104 KB Output is correct
6 Correct 101 ms 65408 KB Output is correct
7 Correct 98 ms 66620 KB Output is correct
8 Correct 96 ms 67476 KB Output is correct
9 Correct 98 ms 68416 KB Output is correct
10 Correct 97 ms 69480 KB Output is correct
11 Correct 116 ms 70684 KB Output is correct
12 Correct 119 ms 71644 KB Output is correct
13 Correct 92 ms 72852 KB Output is correct
14 Correct 111 ms 73912 KB Output is correct
15 Correct 94 ms 74828 KB Output is correct
16 Correct 92 ms 75756 KB Output is correct
17 Correct 87 ms 76944 KB Output is correct
18 Correct 86 ms 78036 KB Output is correct