제출 #527025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527025		inluminas	Building Bridges (CEOI17_building)	C++17	100 / 100	63 ms	8496 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 ll lmt=1e5+2;
ll 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,ll L=1,ll R=n,ll at=1){
  ll 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,ll L=1,ll R=n,ll at=1){
  ll 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(ll i=1;i<=n;i++){
    cin>>h[i];
    h2[i]=h[i];
  }
  sort(h2+1,h2+n+1);
  ll sum=0;
  for(ll i=1;i<=n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  ll dp=sum-w[1];
  for(ll 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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40