#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const long long INF = 1e18 + 7;
bool queryMode;
long long H[MAX_N], W[MAX_N];
long long dp[MAX_N];
long long divide(long long a, long long b) {
return a / b - (a % b != 0 and (a ^ b) < 0);
}
struct Line {
mutable long long m, c, p;
Line() {}
Line(long long m_, long long c_) : m(m_), c(c_), p(0) {}
Line(long long m_, long long c_, long long p_) : m(m_), c(c_), p(p_) {}
bool operator<(const Line &o) const {
if(queryMode == true) {
return p < o.p;
}
return m < o.m;
}
};
struct LineContainer : multiset <Line> {
bool intersect(iterator now, iterator nxt) {
if(nxt == end()) {
now->p = INF;
return false;
}
if(now->m == nxt->m) {
now->p = -INF;
if(now->c > nxt->c) {
now->p = INF;
}
}
else {
now->p = divide(now->c - nxt->c, nxt->m - now->m);
}
return now->p >= nxt->p;
}
void addLine(Line f) {
auto nxt = insert(f), now = nxt++, prv = now;
while(intersect(now, nxt) == true) {
nxt = erase(nxt);
}
if(prv != begin() and intersect(--prv, now) == true) {
intersect(prv, now = erase(now));
}
while((now = prv) != begin() and (--prv)->p >= now->p) {
intersect(prv, erase(now));
}
}
long long query(long long x) {
queryMode = true;
auto it = lower_bound({-INF, -INF, x});
queryMode = false;
return it->m * x + it->c;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N;
cin >> N;
long long sumW = 0;
for(int i = 1; i <= N; i++) {
cin >> H[i];
}
for(int i = 1; i <= N; i++) {
cin >> W[i];
sumW += W[i];
}
LineContainer cht;
dp[1] = -W[1];
cht.addLine({2 * H[1], -H[1] * H[1] - dp[1]});
for(int i = 2; i <= N; i++) {
dp[i] = -cht.query(H[i]) + H[i] * H[i] - W[i];
cht.addLine({2 * H[i], -H[i] * H[i] - dp[i]});
}
cout << sumW + dp[N];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
3684 KB |
Output is correct |
2 |
Correct |
49 ms |
3644 KB |
Output is correct |
3 |
Correct |
39 ms |
3648 KB |
Output is correct |
4 |
Correct |
34 ms |
3568 KB |
Output is correct |
5 |
Correct |
36 ms |
4732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
39 ms |
3684 KB |
Output is correct |
7 |
Correct |
49 ms |
3644 KB |
Output is correct |
8 |
Correct |
39 ms |
3648 KB |
Output is correct |
9 |
Correct |
34 ms |
3568 KB |
Output is correct |
10 |
Correct |
36 ms |
4732 KB |
Output is correct |
11 |
Correct |
36 ms |
3884 KB |
Output is correct |
12 |
Correct |
37 ms |
3668 KB |
Output is correct |
13 |
Correct |
31 ms |
3728 KB |
Output is correct |
14 |
Correct |
39 ms |
3884 KB |
Output is correct |
15 |
Correct |
67 ms |
9688 KB |
Output is correct |
16 |
Correct |
35 ms |
4772 KB |
Output is correct |
17 |
Correct |
20 ms |
3668 KB |
Output is correct |
18 |
Correct |
22 ms |
3700 KB |
Output is correct |