oj.uz

Submission #711364

# Submission time Handle Problem Language Result Execution time Memory
711364 2023-03-16T17:51:12 Z Pacybwoah Building Bridges (CEOI17_building) C++14
100 / 100
 122 ms 66400 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    ll m,b;
    ll val(ll x){
        return m*x+b;
    }
    node(ll _m,ll _b){
        m=_m;
        b=_b;
    }
};
vector<node> seg(4000014,node(0,1e18));
void insert(ll l,ll r,node line,int ind){
    if(l==r){
        if(seg[ind].val(l)>line.val(l)) seg[ind]=line;
        return ;
    }
    ll mid=(l+r)>>1;
    if(seg[ind].m<line.m) swap(seg[ind],line);
    if(line.val(mid)<seg[ind].val(mid)){
        insert(l,mid,seg[ind],ind*2);
        seg[ind]=line;
    }
    else{
        insert(mid+1,r,line,ind*2+1);
    }
}
ll query(int l,int r,ll pos,int ind){
    int mid=(l+r)>>1;
    if(l==r) return seg[ind].val(pos);
    if(pos<=mid){
        return min(query(l,mid,pos,ind*2),seg[ind].val(pos));
    }
    else{
        return min(query(mid+1,r,pos,ind*2+1),seg[ind].val(pos));
    }
}
int main(){
    int n;
    cin>>n;
    vector<ll> dp(n),h(n),w(n);
    ll sum=0;
    for(int i=0;i<n;i++) cin>>h[i];
    for(int i=0;i<n;i++) cin>>w[i],sum+=w[i];
    dp[0]=-w[0];
    insert(0,1000000,node(-2*h[0],dp[0]+h[0]*h[0]),1);
    for(int i=1;i<n;i++){
        dp[i]=query(0,1000000,h[i],1)+h[i]*h[i]-w[i];
        insert(0,1000000,node(-2*h[i],dp[i]+h[i]*h[i]),1);
    }
    cout<<dp[n-1]+sum<<"\n";
    //for(auto x:dp) cout<<x<<" ";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62796 KB Output is correct
3 Correct 26 ms 62824 KB Output is correct
4 Correct 29 ms 62952 KB Output is correct
5 Correct 29 ms 62896 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 65272 KB Output is correct
2 Correct 122 ms 65268 KB Output is correct
3 Correct 97 ms 65276 KB Output is correct
4 Correct 86 ms 65224 KB Output is correct
5 Correct 105 ms 65272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62796 KB Output is correct
3 Correct 26 ms 62824 KB Output is correct
4 Correct 29 ms 62952 KB Output is correct
5 Correct 29 ms 62896 KB Output is correct
6 Correct 110 ms 65272 KB Output is correct
7 Correct 122 ms 65268 KB Output is correct
8 Correct 97 ms 65276 KB Output is correct
9 Correct 86 ms 65224 KB Output is correct
10 Correct 105 ms 65272 KB Output is correct
11 Correct 114 ms 66400 KB Output is correct
12 Correct 116 ms 66280 KB Output is correct
13 Correct 100 ms 66384 KB Output is correct
14 Correct 109 ms 66392 KB Output is correct
15 Correct 93 ms 66020 KB Output is correct
16 Correct 98 ms 66124 KB Output is correct
17 Correct 84 ms 66284 KB Output is correct
18 Correct 83 ms 66344 KB Output is correct