#include <bits/stdc++.h>
using namespace std;
long long w[100005] , h[100005];
long long n;
long long dp[100005];
struct line{
long long x , y;
line(long long x , long long y){
this->x = x , this->y = y;
}
};
template <class type>
class CHT{
public :
bool cmp(type a , type b , type c){
double f1 = ((c.y) - (a.y)) * ((a.x) - (b.x)) , f2 = ((b.y) - (a.y)) * ((a.x) - (c.x));
return ((double)((double) (c.y) - (a.y)) / ((double) (b.y) - (a.y)) ) <= ((double) ((double) (a.x) - (c.x)) / ((double) (a.x) - (b.x)) );
return f1 <= f2;
}
int returnsize(){
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);
}
long long eval(type b , int a){
int w = (b.x) * a + (b.y);
return w;
}
long long querymin(int x){
if(cht.size() == 0) return ((long long) 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;
}
long long 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;
}
void merge(vector<type> nhcht){
vector<type> newcht;
int A = 0 , B = 0;
for(int i = 0 ; i < (nhcht.size() + cht.size()) ; i++){
if(A == nhcht.size()){
while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , cht[B])){
newcht.pop_back();
}
newcht.push_back(cht[B]);
++B;
}
else if(B == cht.size()){
while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , nhcht[A])){
newcht.pop_back();
}
newcht.push_back(nhcht[A]);
++A;
}
else{
if(cht[B].x > nhcht[A].x){
while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , cht[B])){
newcht.pop_back();
}
newcht.push_back(cht[B]);
++B;
}
else{
while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , nhcht[A])){
newcht.pop_back();
}
newcht.push_back(nhcht[A]);
++A;
}
}
}
cht = newcht;
}
vector<type> mergefunc(){
return cht;
}
void clearv(){
cht.clear();
}
long long querymax(int x){
if(cht.size() == 0) return 0;
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;
}
long long bestvalue = eval(cht.front() , x);
if(ansj != -1) bestvalue = max(bestvalue , eval(cht[ansj] , x));
ansj++;
if(ansj < cht.size()) bestvalue = max(bestvalue ,eval(cht[ansj] , x));
return bestvalue;
}
// private :
vector<type> cht;
};
CHT<line> chts[32];
void addline(line a){
chts[0].addLINE(a);
for(int i = 0 ; i < 32 ; i++){
if((chts[i].returnsize()) > (1LL<<i)){
chts[i+1].merge(chts[i].mergefunc());
chts[i].clearv();
}
}
}
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;
}
int 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] + dp[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]);
}
Compilation message
building.cpp: In instantiation of 'void CHT<type>::merge(std::vector<_Tp>) [with type = line]':
building.cpp:126:39: required from here
building.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < (nhcht.size() + cht.size()) ; i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:58:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(A == nhcht.size()){
building.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if(B == cht.size()){
building.cpp: In instantiation of 'long long int CHT<type>::querymin(int) [with type = line]':
building.cpp:136:49: required from here
building.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));
building.cpp: In function 'int main()':
building.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld" , &n);
~~~~~^~~~~~~~~~~~~
building.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld" , &h[i]);
~~~~~^~~~~~~~~~~~~~~~
building.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld" , &w[i]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
4004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
