#include <bits/stdc++.h>
#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 1e5 + 5;
const lli INF = 1e17;
struct Line {
lli a, b;
Line() {}
Line(lli aa, lli bb) : a(aa), b(bb) {}
ld intersect(Line &oth) {
return (ld)(oth.b - b) / (a - oth.a);
}
lli eval(lli x) {
return a * x + b;
}
bool operator<(Line &oth) {
return a < oth.a;
}
void print() {
cout << a << " x + " << b << "\n";
}
};
struct Node {
Line x;
int lc, rc;
Node() : x(Line(0, INF)), lc(-1), rc(-1) {}
};
struct LiChao {
const int MX = 1e6 + 5;
vector<Node> st;
int pt;
int create_node() {
st.pb(Node());
return pt++;
}
void reset() {
pt = 0;
st.clear();
create_node();
}
void extend(int v) {
if(st[v].lc == -1) st[v].lc = create_node();
if(st[v].rc == -1) st[v].rc = create_node();
}
void update(int tl, int tr, int v, Line nw) {
if(tl == tr) {
if(nw.eval(tl) < st[v].x.eval(tl)) {
st[v].x = nw;
}
return;
}
extend(v);
int tm = (tl + tr) >> 1;
if(nw.a > st[v].x.a) {
swap(nw, st[v].x);
}
ld inter = nw.intersect(st[v].x);
if(inter < (ld)tm) {
swap(st[v].x, nw);
update(tl, tm, st[v].lc, nw);
}
else {
update(tm + 1, tr, st[v].rc, nw);
}
}
void update(Line nw) {
// nw.print();
update(0, MX, 0, nw);
}
lli query(int tl, int tr, int v, int ind) {
if(tl == tr) {
return st[v].x.eval(ind);
}
int tm = (tl + tr) >> 1;
extend(v);
if(ind <= tm) {
return min(query(tl, tm, st[v].lc, ind), st[v].x.eval(ind));
}
else {
return min(query(tm + 1, tr, st[v].rc, ind), st[v].x.eval(ind));
}
}
lli query(int ind) {
return query(0, MX, 0, ind);
}
};
LiChao st;
vector<int> h(N), w(N);
vector<lli> dp(N, INF), pr(N, 0);
void solve() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> h[i];
}
for(int i = 1; i <= n; i++) {
cin >> w[i];
}
for(int i = 1; i <= n; i++) {
pr[i] = pr[i - 1] + w[i];
}
dp[1] = 0;
st.reset();
st.update(Line(-2 * h[1], h[1] * h[1] - pr[1] + dp[1]));
for(int i = 2; i <= n; i++) {
dp[i] = st.query(h[i]) + pr[i - 1] + h[i] * h[i];
st.update(Line(-2 * h[i], h[i] * h[i] - pr[i] + dp[i]));
}
cout << dp[n];
}
signed main() {
fastio();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
4756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
