oj.uz

Submission #711360

# Submission time Handle Problem Language Result Execution time Memory
711360 2023-03-16T17:35:53 Z Pacybwoah Building Bridges (CEOI17_building) C++14
0 / 100
 116 ms 66296 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,0));
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";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62796 KB Output is correct
2 Correct 27 ms 62920 KB Output is correct
3 Correct 27 ms 62916 KB Output is correct
4 Correct 34 ms 62932 KB Output is correct
5 Incorrect 34 ms 62936 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 66272 KB Output is correct
2 Correct 100 ms 66296 KB Output is correct
3 Correct 116 ms 66280 KB Output is correct
4 Correct 98 ms 66164 KB Output is correct
5 Incorrect 95 ms 66132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62796 KB Output is correct
2 Correct 27 ms 62920 KB Output is correct
3 Correct 27 ms 62916 KB Output is correct
4 Correct 34 ms 62932 KB Output is correct
5 Incorrect 34 ms 62936 KB Output isn't correct
6 Halted 0 ms 0 KB -