#include <algorithm>
#include <cstdio>
#include <cstring>
#include <tuple>
#include <vector>
using namespace std;
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define MAXN 100000
struct Line {
long m, c;
long operator()(long x) { return m * x + c; }
bool operator<(Line a) const { return a.m != m ? c < a.c : a.m < m; }
};
long intersect(Line a, Line b) {
long num = b.c - a.c, dem = a.m - b.m;
return num / dem - ((num ^ dem) < 0 && num % dem);
}
const long INF = 1e18;
struct hull {
vector<pair<long, Line>> lines;
vector<Line> all;
hull(Line l) : lines{{-INF, l}}, all{l} {}
hull(hull &a, hull &b) {
all.resize(a.size() + b.size());
merge(a.all.begin(), a.all.end(), b.all.begin(), b.all.end(), all.begin());
lines.reserve(all.size());
lines.push_back({-INF, *all.begin()});
for (int i = 1; i < (int) all.size(); ++i) {
auto l = all[i];
if (lines.back().second.m == l.m) continue;
while (lines.size() >= 2) {
auto al = lines[lines.size() - 2].second;
auto bl = lines[lines.size() - 1].second;
if (intersect(bl, l) <= intersect(al, bl)) {
lines.pop_back();
} else break;
}
lines.emplace_back(intersect(lines.back().second, l), l);
}
}
long query(long x) {
return prev(lower_bound(lines.begin(), lines.end(), pair{x, Line{}}, [&](auto a, auto b) {
return a.first < b.first;
}))->second(x);
}
size_t size() { return all.size(); }
};
struct hulls {
vector<hull> h;
void add_line(Line x) {
h.emplace_back(x);
while (h.size() >= 2 && h[h.size() - 2].size() == h[h.size() - 1].size()) {
auto a = h[h.size() - 2];
auto b = h[h.size() - 1];
h.pop_back();
h.pop_back();
h.emplace_back(a, b);
}
}
long query(long x) {
long ret = INF;
for (auto &u : h)
ret = min(ret, u.query(x));
return ret;
}
} cht;
int n, h[MAXN], w[MAXN];
long dp[MAXN];
int main() {
scanf("%d", &n);
forn (i, n) scanf("%d", h + i);
forn (i, n) scanf("%d", w + i);
long wsum = 0;
forn (i, n) wsum += w[i];
// dp[i] =
// = min_{j < i} dp[j] + (h[j] - h[i]) ^ 2 + w[i]
// = min_{j < i} dp[j] + h[j] ^ 2 - 2h[j]h[i] + h[i] ^ 2 + w[i]
// f_j(x) := h[j] ^ 2 - 2h[j]x + dp[j]
// = h[i] ^ 2 + w[i] + min_{j < i} f_j(h[i])
cht.add_line({-2l * h[0], 1l * h[0] * h[0] - w[0]});
for (int i = 1; i < n; ++i) {
dp[i] = 1l * h[i] * h[i] - w[i] + cht.query(h[i]);
cht.add_line({-2l * h[i], 1l * h[i] * h[i] + dp[i]});
}
printf("%ld\n", dp[n - 1] + wsum);
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
building.cpp:79:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | forn (i, n) scanf("%d", h + i);
| ~~~~~^~~~~~~~~~~~~
building.cpp:80:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | forn (i, n) scanf("%d", w + i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
2964 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
