#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Line {
bool type;
double x;
ll m, c;
};
bool operator<(Line l1, Line l2) {
if (l1.type || l2.type) return l1.x < l2.x;
return l1.m > l2.m;
}
set<Line> cht;
ll h[100001], w[100001], tot = 0, dp[100001];
bool has_prev(set<Line>::iterator it) { return it != cht.begin(); }
bool has_next(set<Line>::iterator it) {
return it != cht.end() && next(it) != cht.end();
}
double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
return (double)(l1->c - l2->c) / (l2->m - l1->m);
}
void calc_x(set<Line>::iterator it) {
if (has_prev(it)) {
Line l = *it;
l.x = intersect(prev(it), it);
cht.erase(it);
cht.insert(l);
}
}
bool bad(set<Line>::iterator it) {
// if (has_next(it) && next(it)->c <= it->c) return true;
return (has_prev(it) && has_next(it) &&
intersect(prev(it), next(it)) <= intersect(prev(it), it));
}
void add_line(ll m, ll c) {
set<Line>::iterator it;
it = cht.lower_bound({0, 0, m, c});
if (it != cht.end() && it->m == m) {
if (it->c <= c) return;
cht.erase(it);
}
it = cht.insert({0, 0, m, c}).first;
if (bad(it)) cht.erase(it);
else {
while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
while (has_next(it) && bad(next(it))) cht.erase(next(it));
if (has_next(it)) calc_x(next(it));
calc_x(it);
}
}
ll query(ll h) {
Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
return l.m * h + l.c;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) {
cin >> w[i];
tot += w[i];
}
dp[1] = -w[1];
for (int i = 2; i <= n; i++) {
add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
dp[i] = query(h[i]) - w[i] + h[i] * h[i];
}
cout << tot + dp[n];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
3900 KB |
Output is correct |
2 |
Correct |
71 ms |
3676 KB |
Output is correct |
3 |
Correct |
60 ms |
3672 KB |
Output is correct |
4 |
Correct |
57 ms |
3664 KB |
Output is correct |
5 |
Correct |
64 ms |
5268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
60 ms |
3900 KB |
Output is correct |
7 |
Correct |
71 ms |
3676 KB |
Output is correct |
8 |
Correct |
60 ms |
3672 KB |
Output is correct |
9 |
Correct |
57 ms |
3664 KB |
Output is correct |
10 |
Correct |
64 ms |
5268 KB |
Output is correct |
11 |
Correct |
53 ms |
3932 KB |
Output is correct |
12 |
Correct |
61 ms |
3676 KB |
Output is correct |
13 |
Correct |
39 ms |
3672 KB |
Output is correct |
14 |
Correct |
59 ms |
4040 KB |
Output is correct |
15 |
Correct |
73 ms |
11344 KB |
Output is correct |
16 |
Correct |
57 ms |
5260 KB |
Output is correct |
17 |
Correct |
12 ms |
3676 KB |
Output is correct |
18 |
Correct |
15 ms |
3736 KB |
Output is correct |