#include <bits/stdc++.h>
#define int long long
#define lint __int128_t
#define rep(i,n) for(int i =0; i<n;i++)
#define all(a) a.begin(), a.end()
using namespace std;
const int MOD = 32768;
struct line
{
mutable long double xleft = -1e15;
bool search=false;
int a,b;
line(int x) : b(x), search(true) {}
line(int ia, int ib) : a(ia), b(ib) {}
bool operator<(const line& l2) const {
if(search) return b < l2.xleft;
if(l2.search) return xleft < l2.b;
return (a!=l2.a)?a<l2.a:b<l2.b;
}
int eval(int x) const {return a*x + b;}
// it zeigt auf Element eins links
void recalcleft(set<line>::iterator it) const
{
if(a == it -> a) return;
xleft = ((long double) b - it->b) / ((long double) it->a - a);
}
};
struct hullopt
{
set<line>hull;
bool bad(set<line>::iterator it)
{
// normal case
if(it==hull.begin()) {
if(next(it)==hull.end()) return false;
return it->a==next(it)->a&&next(it)->b>=it->b;
}
auto pr = prev(it);
auto nx = next(it);
if(pr->a==it->a) return it->b<=pr->b; //not like joel
if(nx->a==it->a) return it->b<=nx->b;
return ((lint) pr->a - it->a)*((lint) nx->b - it->b)<=((lint) it->a-nx->a)*((lint)it->b-pr->b);
}
void insert(int a, int b)
{
auto it = hull.insert(line({-a,-b})).first;
if(bad(it)) {hull.erase(it); return;}
while (it!=hull.begin()&&bad(prev(it))) hull.erase(prev(it));
while (next(it)!=hull.end()&&bad(next(it))) hull.erase(next(it));
// why don't I have to do this previously
if(it==hull.begin()) it->xleft=-1e15;
else it->recalcleft(prev(it));
if(next(it)!=hull.end()) next(it)->recalcleft(it);
}
int query(int x)
{
return -prev(hull.upper_bound(line(x)))->eval(x);
}
};
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin>>n;
vector<int>h(n),w(n);
rep(i,n) cin>>h[i];
rep(i,n) cin>>w[i];
int sum = 0;
rep(i,n-1) sum+=w[i+1];
vector<int>dp(n,1e18);
dp[0]=0;
hullopt opt = hullopt();
opt.insert(-2*h[0], dp[0]+h[0]*h[0]);
for(int i = 1; i < n; i++)
{
dp[i] = h[i]*h[i] - w[i] + opt.query(h[i]);
opt.insert(-2*h[i], dp[i]+h[i]*h[i]);
}
cout<<dp[n-1]+sum<<'\n';
}
Compilation message
building.cpp: In constructor 'line::line(long long int)':
building.cpp:16:19: warning: 'line::b' will be initialized after [-Wreorder]
16 | int a,b;
| ^
building.cpp:15:18: warning: 'bool line::search' [-Wreorder]
15 | bool search=false;
| ^~~~~~
building.cpp:18:13: warning: when initialized here [-Wreorder]
18 | line(int x) : b(x), search(true) {}
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
3712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
