| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 48424 | wzy | Building Bridges (CEOI17_building) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
long long w[100005] , h[100005];
long long n;
long long dp[100005];
struct line{
int x , y;
line(int x , int y){
this->x = x , this->y = y;
}
};
bool operator <(line a , line b){
if(a.x == b.x) return a.y > b.y;
else return a.x > b.x;
}
template <class type>
class CHT{
public :
bool cmp(type a , type b , type c){
return ((double)((double) (c.y) - (a.y)) * ((double) (a.x) - (b.x)) <= ((double) ((double) (a.x) - (c.x)) * ((double) (b.y) - (a.y)) ) ) ;
}
int sizex(){
return cht.size();
}
void addLINE(type a){
while(cht.size() >= 2 && cmp(cht[cht.size() - 2] , cht[cht.size() - 1] , a)){
cht.pop_back();
}
cht.push_back(a);
}
int eval(type b , int a){
int w = (b.x) * a + (b.y);
return w;
}
void merge(vector<type> nhcht){
vector<type> newcht;
for(int i = 0 ; i < nhcht.size() + cht.size() ; i++) newcht.pb(line(0,0));
std::merge(nhcht.begin() , nhcht.end() , cht.begin() , cht.end() , newcht.begin() );
cht.clear();
for(int i = 0 ; i < newcht.size() ; i++) addLINE(newcht[i]);
}
int querymin(int x){
if(cht.size() == 0) return (int) 1e18;
int l = 0 , r = cht.size() - 1;
r--;
int ansj = -1;
while(l<=r){
int mid = (l+r)/2;
if(eval(cht[mid] , x) >= eval(cht[mid + 1] , x)){
l = mid + 1;
ansj = mid;
}
else r = mid - 1;
}
int bestvalue = eval(cht.front() , x);
if(ansj != -1) bestvalue = min(bestvalue , eval(cht[ansj] , x));
ansj ++;
if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));
return bestvalue;
}
vector<type> vectorT(){
return cht;
}
void clearv(){
cht.clear();
}
vector<type> cht;
};
CHT <line> chts;
void addline(line a){
vector<line> v;
v.push_back(a);
chts[0].merge(v);
for(int i = 0 ; i < 32 ; i++){
int z = (1LL<<i);
if(chts[i].sizex() > z){
chts[i+1].merge(chts[i].vectorT());
chts[i].clearv();
}
}
return ;
}
long long query(int x){
long long bestvalue = (long long) 1e18;
for(int i = 0 ; i < 32 ; i++){
bestvalue = min(bestvalue , chts[i].querymin(x));
}
return bestvalue;
}
int32_t main(){
scanf("%lld" , &n);
dp[0] = 0;
for(int i = 1 ; i <=n ;i ++){
scanf("%lld" , &h[i]);
}
w[0] = 0;
for(int i = 1 ; i <=n ;i ++){
scanf("%lld" , &w[i]);
w[i] += w[i-1];
}
dp[1] = 0;
addline(line(-2*h[1] , h[1]*h[1] - w[1] ));
for(int i = 2 ; i <= n ;i ++){
dp[i] = query(h[i]) + h[i]*h[i] + w[i-1];
addline(line(-2*h[i] , h[i]*h[i] - w[i] + dp[i]));
}
printf("%lld\n" , dp[n]);
}