#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)1e5+10;
const int mxC = (int)1e6+10;
const int LINF = (int)1e12+10;
int n, m, x, h[mxN], w[mxN], dp[mxN];
struct Line{
int m, c;
Line(){ m=c=LINF; }
Line(int _m, int _c){ m = _m, c = _c;}
int operator()(int x){ return m*x+c; }
} seg[2*mxC+10];
void addLine(Line a, int p=0, int l=1, int r=mxC){
if(l==r){
if(seg[p](l)>a(l)) seg[p]=a;
return;
}
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
if(a.m > seg[p].m) swap(a,seg[p]);
if(a(mid) < seg[p](mid))
swap(a,seg[p]), addLine(a,p+1,l,mid);
else addLine(a,rp,mid+1,r);
}
int query(int x, int p=0, int l=1, int r=mxC){
if(l==r) return seg[p](x);
int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
if(x<=mid) return min(query(x,p+1,l,mid),seg[p](x));
return min(query(x,rp,mid+1,r),seg[p](x));
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++) cin >> w[i];
dp[1] = -w[1];
for(int i = 1; i <= n; i++){
if(i>1)dp[i] = query(h[i])+h[i]*h[i]-w[i];
addLine({-2*h[i],dp[i]+h[i]*h[i]});
}
cout << accumulate(w+1,w+n+1,0ll)+dp[n];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
33372 KB |
Output is correct |
2 |
Correct |
6 ms |
33372 KB |
Output is correct |
3 |
Correct |
5 ms |
33368 KB |
Output is correct |
4 |
Correct |
6 ms |
33440 KB |
Output is correct |
5 |
Correct |
7 ms |
33372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
33884 KB |
Output is correct |
2 |
Correct |
40 ms |
34908 KB |
Output is correct |
3 |
Correct |
37 ms |
34908 KB |
Output is correct |
4 |
Correct |
34 ms |
35024 KB |
Output is correct |
5 |
Correct |
31 ms |
34904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
33372 KB |
Output is correct |
2 |
Correct |
6 ms |
33372 KB |
Output is correct |
3 |
Correct |
5 ms |
33368 KB |
Output is correct |
4 |
Correct |
6 ms |
33440 KB |
Output is correct |
5 |
Correct |
7 ms |
33372 KB |
Output is correct |
6 |
Correct |
36 ms |
33884 KB |
Output is correct |
7 |
Correct |
40 ms |
34908 KB |
Output is correct |
8 |
Correct |
37 ms |
34908 KB |
Output is correct |
9 |
Correct |
34 ms |
35024 KB |
Output is correct |
10 |
Correct |
31 ms |
34904 KB |
Output is correct |
11 |
Correct |
41 ms |
35276 KB |
Output is correct |
12 |
Correct |
40 ms |
34908 KB |
Output is correct |
13 |
Correct |
36 ms |
35160 KB |
Output is correct |
14 |
Correct |
41 ms |
35160 KB |
Output is correct |
15 |
Correct |
33 ms |
34960 KB |
Output is correct |
16 |
Correct |
31 ms |
34904 KB |
Output is correct |
17 |
Correct |
24 ms |
35164 KB |
Output is correct |
18 |
Correct |
23 ms |
35164 KB |
Output is correct |