#include <bits/stdc++.h>
const int MAXN = 1e5;
const long long INF = 1e18;
int h[1 + MAXN], w[1 + MAXN];
long long d[1 + MAXN];
class Batch{
private:
struct Line{
long long a, b;
inline long long get(long long x) {
return 1LL * a * x + b;
}
};
struct LiChao{
LiChao *st, *dr;
Line l;
LiChao(){
st = dr = NULL;
l = {0, INF};
}
}*root;
public:
Batch() {root = new LiChao();}
inline void fix(LiChao *nod) {
if(nod -> st == NULL) nod -> st = new LiChao();
if(nod -> dr == NULL) nod -> dr = new LiChao();
}
void add(LiChao *nod, long long left, long long right, Line l) {
fix(nod);
Line &curr = nod -> l;
if(l.get(left) <= curr.get(left) && l.get(right) <= curr.get(right)){curr = l; return;}
if(l.get(left) >= curr.get(left) && l.get(right) >= curr.get(right)) return;
long long mid = (left + right) / 2;
if(curr.get(left) > l.get(left))
std::swap(l, curr);
if(curr.get(mid) > l.get(mid)){
std::swap(l, curr);
add(nod -> st, left, mid, l);
}
else add(nod -> dr, mid + 1, right, l);
}
long long query(LiChao *nod, long long left, long long right, long long x) {
fix(nod);
long long val = nod -> l.get(x);
if(left == right) return val;
long long mid = (left + right) / 2;
if(x <= mid) return std::min(val, query(nod -> st, left, mid, x));
return std::min(val, query(nod -> dr, mid + 1, right, x));
}
void add(Line l){add(root, 0, 1e9, l);}
long long query(long long x){return query(root, 0, 1e9, x);}
};
int main(){
FILE*fi,*fo;
fi = fopen("a.in","r");
fo = fopen("a.out","w");
int n;
fscanf(fi,"%d", &n);
for(int i = 1; i <= n; i++)
fscanf(fi,"%d", &h[i]);
long long sum = 0;
for(int i = 1; i <= n; i++) {
fscanf(fi,"%d", &w[i]);
sum += w[i];
}
/*
d[i] = d[j] + (h[i] - h[j])^2 + sum(k = j + 1, i - 1)w[i]
d[i] = -2h[j] * h[i] + (h[j] * h[j] + d[j]) + h[i] * h[i] - w[i] + sum(k = j + 1, i - 1)w[i]
*/
Batch hull;
hull.add({-2 * h[1], 1LL * h[1] * h[1] - w[1]});
for(int i = 2; i <= n; i++) {
d[i] = hull.query(h[i]) + 1LL * h[i] * h[i] - w[i];
hull.add({-2 * h[i], 1LL * h[i] * h[i] + d[i]});
}
fprintf(fo,"%lld", d[n] + sum);
return 0;
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:71:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fi,"%d", &n);
~~~~~~^~~~~~~~~~~~~
building.cpp:73:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fi,"%d", &h[i]);
~~~~~~^~~~~~~~~~~~~~~~
building.cpp:77:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fi,"%d", &w[i]);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
