oj.uz

Submission #426792

# Submission time Handle Problem Language Result Execution time Memory
426792 2021-06-14T09:50:44 Z oleh1421 Building Bridges (CEOI17_building) C++17
100 / 100
 74 ms 7496 KB 
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> line;

const int N=1000010;
const ll mod=1000000007;
const ll inf=1e15;
ll h[N],w[N];
ll dp[N];
ll a[N],b[N];
line t[N];
ll f(line cur,ll x){
    return cur.first*x+cur.second;
}
int TOT=1;
int L[N],R[N];
void upd(int v,int l,int r,line cur){
//    cout<<v<<" "<<l<<" "<<r<<endl;

    ll mid=(l+r)/2;
    if (f(t[v],mid)>f(cur,mid)) swap(t[v],cur);
    if (cur.second==inf || l==r) return;
    if (f(t[v],l)>f(cur,l)){
        if (!L[v]) {
            L[v]=++TOT;
            t[TOT]={1e9,inf};
        }
        upd(L[v],l,mid,cur);
    } else {
        if (!R[v]) {
            R[v]=++TOT;
            t[TOT]={1e9,inf};
        }
        upd(R[v],mid+1,r,cur);
    }
}
ll get(int v,int l,int r,int pos){
//    cout<<v<<" "<<l<<" "<<r<<endl;
    if (l==r) return f(t[v],pos);
    if (!v) return inf;
    int mid=(l+r)/2;
    if (pos<=mid) return min(f(t[v],pos),get(L[v],l,mid,pos));
    else return min(f(t[v],pos),get(R[v],mid+1,r,pos));
}
int main(){
    t[0]={1e9,inf};
    t[1]={1e9,inf};
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for (int i=1;i<=n;i++) cin>>h[i];
    for (int i=1;i<=n;i++) cin>>w[i],w[i]+=w[i-1];
    dp[1]=0;
    a[1]=h[1]*h[1]-w[1]+dp[1];
    b[1]=-2*h[1];
    upd(1,0,1e9,{b[1],a[1]});
//    cout<<"Line "<<b[1]<<" "<<a[1]<<endl;
    for (int i=2;i<=n;i++){
        dp[i]=min(inf,get(1,0,1e9,h[i]));
//        for (int j=1;j<i;j++){
//            dp[i]=min(dp[i],a[j]+b[j]*h[i]);
//        }
        dp[i]+=h[i]*h[i]+w[i-1];
//        cout<<i<<" "<<dp[i]<<endl;
        a[i]=h[i]*h[i]+dp[i]-w[i];
        b[i]=-2*h[i];
        upd(1,0,1e9,{b[i],a[i]});
//        cout<<"Line "<<b[i]<<" "<<a[i]<<endl;
    }
    cout<<dp[n]<<endl;
    return 0;
}
/**
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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4476 KB Output is correct
2 Correct 69 ms 4452 KB Output is correct
3 Correct 69 ms 4440 KB Output is correct
4 Correct 65 ms 4348 KB Output is correct
5 Correct 51 ms 5700 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 69 ms 4476 KB Output is correct
7 Correct 69 ms 4452 KB Output is correct
8 Correct 69 ms 4440 KB Output is correct
9 Correct 65 ms 4348 KB Output is correct
10 Correct 51 ms 5700 KB Output is correct
11 Correct 68 ms 5780 KB Output is correct
12 Correct 70 ms 5816 KB Output is correct
13 Correct 55 ms 5340 KB Output is correct
14 Correct 74 ms 5920 KB Output is correct
15 Correct 53 ms 7496 KB Output is correct
16 Correct 52 ms 6704 KB Output is correct
17 Correct 35 ms 5316 KB Output is correct
18 Correct 36 ms 5400 KB Output is correct