Submission #527021

#	Time	Username	Problem	Language	Result	Execution time	Memory
527021		inluminas	Building Bridges (CEOI17_building)	C++17	0 / 100	45 ms	7112 KiB

building

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=1e5+2;
int h[lmt],n,h2[lmt],w[lmt];
vector<pair<ll,ll>>tree(3*lmt,{0,1e14});

ll f(pair<ll,ll>line,ll x){//line.first=m,line.second=c
  return line.first*x+line.second;
}

void update(pair<ll,ll>line,int L=1,int R=n,int at=1){
  int mid=(L+R)>>1;
  bool lft=f(line,h2[L])<f(tree[at],h2[L]);
  bool md=f(line,h2[mid])<f(tree[at],h2[mid]);

  if(md) swap(tree[at],line);

  if(L==R) return;
  else if(lft!=md) update(line,L,mid,at*2);
  else update(line,mid+1,R,at*2+1);
}

ll query(ll x,int L=1,int R=n,int at=1){
  int mid=(L+R)>>1;
  ll cur=f(tree[at],x);
  if(L==R) return cur;
  if(x<=h2[mid]) return min(cur,query(x,L,mid,at*2));
  else return min(cur,query(x,mid+1,R,at*2+1));
}

int main(){
  fastio;

  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>h[i];
    h2[i]=h[i];
  }
  sort(h2+1,h2+n+1);
  ll sum=0;
  for(int i=1;i<=n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  ll dp=sum;
  for(int i=1;i<=n;i++){
    if(i>1) dp=query(h[i])+h[i]*h[i]-w[i];
    update({-2*h[i],dp+h[i]*h[i]});
  }
  cout<<dp<<endl;
  return 0;
}

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