#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
#define MAX_N 1000001
int seg[MAX_N+1];
bool is_set[MAX_N+1];
int total = 0;
void add(int i, int v) {
for (int x=i+1; x<=MAX_N; x+=x&-x) seg[x] += v;
}
int sum(int i) {
int s = 0;
for (int x=i+1; x>0; x-=x&-x) s += seg[x];
return s;
}
int kth(int w) {
if (w <= 0) return 0;
int x = 0;
for (int k=(1<<19); k>0; k/=2) {
if (x+k <= MAX_N && seg[x+k] < w) {
w -= seg[x+k];
x += k;
}
}
return x;
}
inline int p_left(int x) {
int s = sum(x-1);
if (s == 0) return -1;
return kth(s);
}
inline int p_right(int x) {
int s = sum(x);
if (s == total) return -1;
return kth(s+1);
}
int prv[MAX_N*2-1], nxt[MAX_N*2-1];
void set_val(int k, int v) {
if (v) {
int a = p_left(k), b = -1;
if (a != -1) b = nxt[a];
else b = p_right(k);
if (a != -1) nxt[a] = k;
if (b != -1) prv[b] = k;
nxt[k] = b, prv[k] = a;
}
else {
int a = prv[k], b = nxt[k];
if (a != -1) nxt[a] = b;
if (b != -1) prv[b] = a;
prv[k] = nxt[k] = -1;
}
if (v) add(k, 1), total++;
else add(k, -1), total--;
is_set[k] = v;
}
typedef pair<int, long long> P;
P operator -(const P &a, const P &b) { return P(a._1-b._1, a._2-b._2); }
inline long long det(P a, P b) { return 1LL*a._1*b._2 - 1LL*a._2*b._1; }
int N;
int H[100000], W[100000];
long long dp[1000001];
long long f[1000001];
inline P get(int x) { return P(x, f[x]); }
void update(int x, long long y) {
if (dp[x] <= y) return;
if (dp[x] < INF) if (is_set[x]) set_val(x, 0);
P p = P(x, y+1LL*x*x);
dp[x] = y;
f[x] = p._2;
while (true) {
int right = p_right(x);
if (right == -1) break;
P r = get(right);
if (p._2 >= r._2) return; // erase p
else {
if (nxt[right] == -1) break;
P k = get(nxt[right]);
if (det(r-p, k-r) > 0) break;
set_val(right, 0);
}
}
while (true) {
int left = p_left(x);
if (left == -1) break;
P l = get(left);
if (l._2 >= p._2) set_val(left, 0);
else {
if (prv[left] == -1) break;
P k = get(prv[left]);
if (det(l-k, p-l) > 0) break;
set_val(left, 0);
}
}
int right = p_right(x);
if (right != -1 && prv[right] != -1) {
P r = get(right);
P l = get(prv[right]);
if (det(p-l, r-p) <= 0) return;
}
set_val(x, 1);
}
signed main() {
cin >> N;
rep(i, N) cin >> H[i];
long long sum = 0;
rep(i, N) {
cin >> W[i];
sum += W[i];
W[i] = -W[i];
}
rep(h, 1000001) dp[h] = INF, f[h] = INF;
rep(i, MAX_N*2-1) prv[i] = nxt[i] = -1;
update(H[0], W[0]);
for (int i=1; i<N-1; i++) {
long long m = INF;
int st = kth(1);
if (st == -1) continue;
for (int x=st; x!=-1; x=nxt[x]) m = min(m, f[x] - 2LL*x*H[i]);
assert(total <= 2000);
update(H[i], m+1LL*H[i]*H[i]+W[i]);
}
long long m = INF;
rep(h, 1000001) m = min(m, dp[h] + 1LL*(h-H[N-1])*(h-H[N-1]));
cout << sum + m + W[N-1] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
38928 KB |
Output is correct |
| 2 |
Correct |
6 ms |
38928 KB |
Output is correct |
| 3 |
Correct |
6 ms |
38928 KB |
Output is correct |
| 4 |
Correct |
3 ms |
38928 KB |
Output is correct |
| 5 |
Correct |
9 ms |
38928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
539 ms |
38928 KB |
Output is correct |
| 2 |
Correct |
513 ms |
38928 KB |
Output is correct |
| 3 |
Correct |
529 ms |
38928 KB |
Output is correct |
| 4 |
Correct |
196 ms |
38928 KB |
Output is correct |
| 5 |
Runtime error |
86 ms |
38932 KB |
Execution killed because of forbidden syscall gettid (186) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
38928 KB |
Output is correct |
| 2 |
Correct |
6 ms |
38928 KB |
Output is correct |
| 3 |
Correct |
6 ms |
38928 KB |
Output is correct |
| 4 |
Correct |
3 ms |
38928 KB |
Output is correct |
| 5 |
Correct |
9 ms |
38928 KB |
Output is correct |
| 6 |
Correct |
539 ms |
38928 KB |
Output is correct |
| 7 |
Correct |
513 ms |
38928 KB |
Output is correct |
| 8 |
Correct |
529 ms |
38928 KB |
Output is correct |
| 9 |
Correct |
196 ms |
38928 KB |
Output is correct |
| 10 |
Runtime error |
86 ms |
38932 KB |
Execution killed because of forbidden syscall gettid (186) |
