#include <stdio.h>
#include <set>
#include <algorithm>
#define ll long long
#define INF 1e9
#define MINF -INF
#define N 100100
int flag;
ll w[N];
ll h[N];
struct line{
ll m;
ll b;
double start;
double end;
};
struct compare{
bool operator()(line a, line b){
if(!flag){
if(a.m != b.m){
return a.m > b.m;
}else{
return a.b > b.b;
};
}else{
return a.start < b.start;
};
};
};
double is(line a, line b){
return ((double)(a.b - b.b))/((double)(b.m-a.m));
};
std::set<line,compare> hull;
void insert(ll m, ll b, int i){
flag = 0;
//printf("%lld %lld\n",m,b);
line tmp = {m,b,0.0,0.0};
line perf = {m,b,0.0,0.0};
line perfp;
line perfn;
double f1,f2;
int ttm=0;
auto it = (hull.insert(tmp)).first;
auto itn = it;
auto itp = it;
auto itpp =it;
++itn;
if(itn != hull.end() && itp != hull.begin()){
double f1 = is(tmp,*itn);
if(f1 <= itn->start){
hull.erase(tmp);
return;
};
};
if(itp != hull.begin()){
itp--;
while(itp != hull.begin()){
itpp = itp;
itp--;
f1 = is(tmp,*itpp);
f2 = is(tmp,*itp);
if(f1 > f2){
ttm = 1;
break;
};
};
if(ttm){
itpp++;
itp++;
};
hull.erase(itpp,it);
perf.start = is(tmp,*itp);
perfp = *itp;
perfp.end = perf.start;
hull.erase(itp);
hull.insert(perfp);
}else{
perf.start = MINF;
};
if(itn != hull.end()){
itpp = itn;
itn++;
while(itn != hull.end()){
double f1 = is(*itn,*itpp);
double f2 = is(tmp,*itn);
if(f1 > f2)break;
itpp = itn;
itn++;
};
itn = it;
itn++;
hull.erase(itn,itpp);
perf.end= is(tmp,*itpp);
perfn = *itpp;
perfn.start = perf.end;
hull.erase(itpp);
hull.insert(perfn);
}else{
perf.end = INF;
};
hull.erase(tmp);
hull.insert(perf);
};
ll qry(ll x){
flag = 1;
line tmp = {0,0,(double)x,0};
auto it = hull.lower_bound(tmp);
it--;
flag = 0;
if(it->start <= x && it->end >= x){
return it->m * x + it->b;
};
//printf("Error\n");
return -1;
};
int main(void){
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%lld",&h[i]);
};
for(int i = 0;i<n;i++){
scanf("%lld",&w[i]);
if(i != 0){
w[i] += w[i-1];
};
};
ll tmp = 0;
insert(-2 * h[0],0 - w[0] + h[0] * h[0],0);
for(int i = 1;i<n;i++){
/*for(auto j: hull){
printf("%d %lld %lld %f %f\n",i,j.m,j.b,j.start,j.end);
};
*/
tmp = qry(h[i]) + w[i-1] + h[i] * h[i];
insert(-2 * h[i],tmp - w[i] + h[i] * h[i],i);
};
printf("%lld\n",tmp);
return 0;
};
Compilation message
building.cpp: In function 'int main()':
building.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
building.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&h[i]);
~~~~~^~~~~~~~~~~~~~
building.cpp:133:10: 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 |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
86 ms |
2168 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
