oj.uz

Submission #433491

# Submission time Handle Problem Language Result Execution time Memory
433491 2021-06-19T21:47:45 Z JovanK26 Building Bridges (CEOI17_building) C++14
100 / 100
 101 ms 66484 KB 
#include <bits/stdc++.h>

using namespace std;
long long h[100001];
long long w[100001];
long long f[100001];
struct line
{
    long long k,n;
};
long long get(line a,long long x)
{
    return a.k*x+a.n;
}
line tree[4000005];
void add_line(line nw,long long start=0,long long l=0,long long r=1000001)
{
    long long m=(l+r)/2;
    bool left=get(nw,l)<get(tree[start],l);
    bool mid=get(nw,m)<get(tree[start],m);
    if(mid)
    {
        swap(tree[start],nw);
    }
    if(r-l==1)
    {
        return;
    }
    else if(left!=mid)
    {
        add_line(nw,2*start+1,l,m);
    }
    else
    {
        add_line(nw,2*start+2,m,r);
    }
}
long long query(long long x,long long start=0,long long l=0,long long r=1000001)
{
    long long m=(l+r)/2;
    if(r-l==1)
    {
        return get(tree[start],x);
    }
    else if(x<m)
    {
        return min(get(tree[start],x),query(x,2*start+1,l,m));
    }
    else
    {
        return min(get(tree[start],x),query(x,2*start+2,m,r));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin >> n;
    for(long long i=0;i<n;i++)
    {
        cin >> h[i];
        f[i]=1000000000000000000;
    }
    long long tot=0;
    for(long long i=0;i<n;i++)
    {
        cin >> w[i];
        tot+=w[i];
    }
    for(long long i=0;i<4000005;i++)
    {
        tree[i]={0,1000000000000000000};
    }
    f[0]=-w[0];
    add_line({-2*h[0],f[0]+h[0]*h[0]});
    for(long long i=1;i<n;i++)
    {
        f[i]=query(h[i])+h[i]*h[i]-w[i];
        add_line({-2*h[i],f[i]+h[i]*h[i]});
    }
    cout << tot+f[n-1];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62888 KB Output is correct
2 Correct 37 ms 62920 KB Output is correct
3 Correct 36 ms 62860 KB Output is correct
4 Correct 36 ms 62908 KB Output is correct
5 Correct 36 ms 62852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 65220 KB Output is correct
2 Correct 87 ms 66292 KB Output is correct
3 Correct 86 ms 66228 KB Output is correct
4 Correct 82 ms 66112 KB Output is correct
5 Correct 88 ms 66164 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62888 KB Output is correct
2 Correct 37 ms 62920 KB Output is correct
3 Correct 36 ms 62860 KB Output is correct
4 Correct 36 ms 62908 KB Output is correct
5 Correct 36 ms 62852 KB Output is correct
6 Correct 87 ms 65220 KB Output is correct
7 Correct 87 ms 66292 KB Output is correct
8 Correct 86 ms 66228 KB Output is correct
9 Correct 82 ms 66112 KB Output is correct
10 Correct 88 ms 66164 KB Output is correct
11 Correct 101 ms 66484 KB Output is correct
12 Correct 101 ms 66280 KB Output is correct
13 Correct 79 ms 66328 KB Output is correct
14 Correct 99 ms 66372 KB Output is correct
15 Correct 80 ms 66104 KB Output is correct
16 Correct 79 ms 66196 KB Output is correct
17 Correct 71 ms 66232 KB Output is correct
18 Correct 73 ms 66328 KB Output is correct