oj.uz

Submission #882087

# Submission time Handle Problem Language Result Execution time Memory
882087 2023-12-02T15:06:10 Z nghiaaa Building Bridges (CEOI17_building) C++17
100 / 100
 52 ms 66180 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define endl "\n"
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k)
#define sz(a) (int)a.size()
const ll inf=(ll)1<<60;

int n;
const int N=1e5;
const int MAXVAL=1e6;
ll h[N+1];
ll pre[N+1],f[N+1];
struct Line{
    ll a,b;
    ll f(int x)
    {
        return (ll)a*x+b;
    }
    Line(ll a1,ll b1)
    {
        a=a1,b=b1;
    }
    Line()
    {
        a=INT_MAX,b=LLONG_MAX-(ll)INT_MAX*1000000;
    }
};
Line seg[4*MAXVAL];
void add(int node,int l,int r,Line line)
{
    if (l+1==r)
    {
        if (seg[node].f(l)>line.f(l))
            seg[node]=line;
    }
    else{
        int mid=(l+r)>>1;
        if (seg[node].a>line.a||(
            seg[node].a==line.a&&seg[node].b>line.b)) swap(seg[node],line);
        if (seg[node].f(mid)<line.f(mid))
            add((node<<1)+1,l,mid,line);
        else{
            swap(seg[node],line);
            add((node<<1)+2,mid,r,line);
        }
    }
}
ll GET(int node,int l,int r,int x)
{
    if (l+1==r)
        return seg[node].f(x);
    else{
        int mid=(l+r)>>1;
        if (x<mid) return min(seg[node].f(x),GET((node<<1)+1,l,mid,x));
        else return min(seg[node].f(x),GET((node<<1)+2,mid,r,x));
    }
}
void solve()
{
    cin>>n;
    forw(i,1,n) cin>>h[i];
    forw(i,1,n){
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    f[1]=0;
    add(0,0,MAXVAL+1,Line(-2LL*h[1],h[1]*h[1]-pre[1]));
    forw(i,2,n)
    {
        f[i]=GET(0,0,MAXVAL+1,h[i])+pre[i-1]+h[i]*h[i];
        add(0,0,MAXVAL+1,Line(-2LL*h[i],f[i]+h[i]*h[i]-pre[i]));
    }
    cout<<f[n];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cout<<setprecision(6)<<fixed;
    //time_t TIME_TU=clock();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 9 ms 64132 KB Output is correct
4 Correct 11 ms 64088 KB Output is correct
5 Correct 11 ms 64160 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 65400 KB Output is correct
2 Correct 43 ms 65372 KB Output is correct
3 Correct 46 ms 65408 KB Output is correct
4 Correct 40 ms 65400 KB Output is correct
5 Correct 44 ms 65288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64092 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 9 ms 64132 KB Output is correct
4 Correct 11 ms 64088 KB Output is correct
5 Correct 11 ms 64160 KB Output is correct
6 Correct 44 ms 65400 KB Output is correct
7 Correct 43 ms 65372 KB Output is correct
8 Correct 46 ms 65408 KB Output is correct
9 Correct 40 ms 65400 KB Output is correct
10 Correct 44 ms 65288 KB Output is correct
11 Correct 52 ms 66168 KB Output is correct
12 Correct 49 ms 66168 KB Output is correct
13 Correct 43 ms 66168 KB Output is correct
14 Correct 49 ms 66140 KB Output is correct
15 Correct 38 ms 66180 KB Output is correct
16 Correct 38 ms 66140 KB Output is correct
17 Correct 32 ms 66068 KB Output is correct
18 Correct 31 ms 66140 KB Output is correct