//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int64_t MAX_N = 100002;
const int64_t INF = 1e18;
struct line {
int64_t a, b;
line() {}
line(int64_t a, int64_t b):
a(a), b(b) {}
int64_t get(int64_t x) {
return a * x + b;
}
};
class IT {
public:
struct node {
line d;
node *left_child, *right_child;
node() {
d = line(0, INF);
left_child = NULL;
right_child = NULL;
}
void make_children() {
if (left_child==NULL) {
left_child = new node();
right_child = new node();
}
}
};
int64_t st, fn;
node *root;
IT(int64_t _n) {
st = -2*_n;
fn = 2*_n;
root = new node();
}
void upd(line val, int64_t l, int64_t r, node *cur) {
if (l>r)
return;
int64_t mid = (l + r) / 2;
cur->make_children();
if (val.get(l)<=cur->d.get(l) && val.get(r)<=cur->d.get(r))
cur->d = val;
else if (val.get(l)>=cur->d.get(l) && val.get(r)>=cur->d.get(r))
return;
else if (val.get(l)>=cur->d.get(l) && val.get(mid)>=cur->d.get(mid) && l!=r)
upd(val, mid+1, r, cur->right_child);
else if (val.get(l)<=cur->d.get(l) && val.get(mid)<=cur->d.get(mid)) {
if (l!=r)
upd(cur->d, mid+1, r, cur->right_child);
cur->d = val;
}
else if (val.get(r)>=cur->d.get(r) && val.get(mid)>=cur->d.get(mid) && l!=r)
upd(val, l, mid, cur->left_child);
else if (val.get(r)<=cur->d.get(r) && val.get(mid)<=cur->d.get(mid)) {
if (l!=r)
upd(cur->d, l, mid, cur->left_child);
cur->d = val;
}
}
int64_t get(int64_t pos, int64_t l, int64_t r, node *cur) {
if (pos<l || pos>r)
return INF;
cur->make_children();
int64_t res = cur->d.get(pos);
if (l==r)
return res;
int64_t mid = (l + r) / 2;
return min(res, min(get(pos, l, mid, cur->left_child),
get(pos, mid+1, r, cur->right_child)));
}
void upd(line val) {
upd(val, st, fn, root);
}
int64_t get(int64_t pos) {
return get(pos, st, fn, root);
}
};
int64_t n;
int64_t h[MAX_N], w[MAX_N], f[MAX_N];
int64_t sqr(int64_t x) {
return x * x;
}
void enter() {
cin >> n;
for (int64_t i=1; i<=n; ++i) {
cin >> h[i];
}
for (int64_t i=1; i<=n; ++i) {
cin >> w[i];
w[i] += w[i-1];
}
}
void solve() {
IT tr(2*(*max_element(h+1, h+n+1)));
tr.upd(line(-2*h[1], f[1] - w[1] + sqr(h[1])));
for (int64_t i=2; i<=n; ++i) {
f[i] = tr.get(h[i]) + w[i-1] + sqr(h[i]);
tr.upd(line(-2*h[i], f[i] - w[i] + sqr(h[i])));
}
cout << f[n];
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
496 KB |
Output is correct |
3 |
Correct |
2 ms |
564 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
5484 KB |
Output is correct |
2 |
Correct |
73 ms |
6508 KB |
Output is correct |
3 |
Correct |
72 ms |
7668 KB |
Output is correct |
4 |
Correct |
70 ms |
7668 KB |
Output is correct |
5 |
Runtime error |
698 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
496 KB |
Output is correct |
3 |
Correct |
2 ms |
564 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
73 ms |
5484 KB |
Output is correct |
7 |
Correct |
73 ms |
6508 KB |
Output is correct |
8 |
Correct |
72 ms |
7668 KB |
Output is correct |
9 |
Correct |
70 ms |
7668 KB |
Output is correct |
10 |
Runtime error |
698 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |