Submission #964790

#	Time	Username	Problem	Language	Result	Execution time	Memory
964790		Chmayank2009	Building Bridges (CEOI17_building)	C++17	100 / 100	82 ms	67288 KiB

building

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long inf=1e18;
const long long N=1e6+1;
struct Line{
    long long m=0,c=inf;
};
vector<Line>seg(4*1e6+1);
long long calc(Line Li,long long x){
    return Li.m*x+Li.c;
}
void insert(Line Li,long long i=1,long long l=0,long long r=N){
    long long m=l+(r-l)/2;
    long long mid=calc(Li,m)<calc(seg[i],m);
    long long left=calc(Li,l)<calc(seg[i],l);
    if(mid){
        swap(seg[i],Li);
    }
    if(r-l==1) return;
    if(left!=mid){
        insert(Li,2*i,l,m);
    }
    else{
        insert(Li,2*i+1,m,r);
    }
}
long long get(long long x,long long i=1,long long l=0,long long r=N){
    long long m=l+(r-l)/2;
    long long curr=calc(seg[i],x);
    if(r-l==1) return curr;
    if(x<m){
        return min(curr,get(x,2*i,l,m));
    }
    else{
        return min(curr,get(x,2*i+1,m,r));
    }
}
int main(){
    long long n;
    cin>>n;
    vector<long long>h(n+1);
    vector<long long>w(n+1);
    for(long long i=1;i<=n;i++){
        cin>>h[i];
    }
    for(long long i=1;i<=n;i++){
        cin>>w[i];
    }
    vector<long long>suf(n+1);
    suf[n]=w[n];
    for(long long i=n-1;i>0;i--){
        suf[i]=suf[i+1]+w[i];
    }
    vector<long long>dp(n+1);
    Line Li;
    Li.m=-2*h[1];
    Li.c=suf[1]-w[1]+h[1]*h[1];
    dp[1]=0;
    insert(Li);
    for(long long i=2;i<=n;i++){
        //cout<<get(h[i])<<"\n";
        dp[i]=get(h[i])-suf[i]+h[i]*h[i];
        Li.m=-2*h[i];
        Li.c=h[i]*h[i]+dp[i]+suf[i]-w[i];
        insert(Li);
    }
    cout<<dp[n]<<"\n";
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40