#include <bits/stdc++.h>
#define m first
#define c second;
using namespace std;
typedef pair<long long,long long> line;
const long long inf = 102345678901234567;
long long get(line L, int x){ return L.m * x + L.c; }
long long H[100005];
int C[100005];
struct lichao{
int s, e, m;
lichao *l = nullptr, *r = nullptr;
line val = line(0,inf);
lichao(int S, int E){
s = S, e = E, m = (s+e)/2;
}
void create(){
l = new lichao(s, m);
r = new lichao(m+1, e);
}
void insert(line L){
if(get(L, m+1) < get(val, m+1)) swap(L, val); ///make val the dominant one
if(s == e) return;
if(l == nullptr) create();
if(get(L, s) < get(val, s)) l->insert(L); ///L has some chance in l
else r->insert(L); ///L has some chance in r
}
long long query(int x){
if(s == e) return get(val, x);
else{
if(l == nullptr) create();
if(x > m) return min(get(val,x), r->query(x));
else return min(get(val,x), l->query(x));
}
}
} *root;
signed main(){
ios_base::sync_with_stdio(false);
long long ans = 0;
int n; cin >> n;
for(int i = 0;i < n;i++) cin >> H[i];
for(int i = 0;i < n;i++){
cin >> C[i];
ans += C[i];
C[i] *= -1;
}
root = new lichao(0, 1000001);
long long dp = C[0];
root->insert(line(-2*H[0], dp + H[0]*H[0]));
for(int i = 1;i < n;i++){
dp = root->query(H[i]);
dp += H[i]*H[i] + C[i];
root->insert(line(-2*H[i], dp + H[i]*H[i]));
}
cout << dp + ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
3644 KB |
Output is correct |
2 |
Correct |
58 ms |
3536 KB |
Output is correct |
3 |
Correct |
56 ms |
3764 KB |
Output is correct |
4 |
Correct |
50 ms |
2808 KB |
Output is correct |
5 |
Correct |
64 ms |
19576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
56 ms |
3644 KB |
Output is correct |
7 |
Correct |
58 ms |
3536 KB |
Output is correct |
8 |
Correct |
56 ms |
3764 KB |
Output is correct |
9 |
Correct |
50 ms |
2808 KB |
Output is correct |
10 |
Correct |
64 ms |
19576 KB |
Output is correct |
11 |
Correct |
101 ms |
14584 KB |
Output is correct |
12 |
Correct |
97 ms |
14272 KB |
Output is correct |
13 |
Correct |
52 ms |
3068 KB |
Output is correct |
14 |
Correct |
91 ms |
14456 KB |
Output is correct |
15 |
Correct |
66 ms |
27384 KB |
Output is correct |
16 |
Correct |
67 ms |
19580 KB |
Output is correct |
17 |
Correct |
39 ms |
2560 KB |
Output is correct |
18 |
Correct |
40 ms |
2560 KB |
Output is correct |