#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll MOD=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e18+900;
template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }
class ConvexHullDynamic {
typedef long double coef_t, coord_t, val_t;
//Line 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
private:
struct Line {
coef_t a, b;
long double xLeft;
enum Type { line, maxQuery, minQuery } type;
coord_t val;
explicit Line(coef_t aa = 0, coef_t bb = 0) : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {}
val_t valueAt(coord_t x) const { return a * x + b; }
friend bool areParallel(const Line& l1, const Line& l2) { return l1.a == l2.a; }
friend long double intersectX(const Line& l1, const Line& l2) { return areParallel(l1, l2) ? INFINITY : 1.0*(l2.b - l1.b) / (l1.a - l2.a); }
bool operator<(const Line& l2) const {
if (l2.type == line) return this->a < l2.a;
if (l2.type == maxQuery) return this->xLeft < l2.val;
if (l2.type == minQuery) return this->xLeft < l2.val;
assert(0);
return false;
}
};
private:
bool isMax; //whether or not saved envelope is top(search of max value)
std::set<Line> hull; //envelope itself
private:
bool hasPrev(std::set<Line>::iterator it) { return it != hull.begin(); }
bool hasNext(std::set<Line>::iterator it) { return it != hull.end() && std::next(it) != hull.end(); }
bool irrelevant(const Line& l1, const Line& l2, const Line& l3) { return intersectX(l1, l3) <= intersectX(l1, l2); }
bool irrelevant(std::set<Line>::iterator it) {
return hasPrev(it) && hasNext(it) && ((isMax && irrelevant(*std::prev(it), *it, *std::next(it)))
|| (!isMax && irrelevant(*std::next(it), *it, *std::prev(it))));
}
std::set<Line>::iterator updateLeftBorder(std::set<Line>::iterator it) {
if ((isMax && !hasPrev(it)) || (!isMax && !hasNext(it))) return it;
long double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it));
Line buf(*it);
it = hull.erase(it), buf.xLeft = val, it = hull.insert(it, buf);
return it;
}
public:
explicit ConvexHullDynamic() : isMax(true) {} // true is for max and false is for min
void addLine(coef_t a, coef_t b) {
Line l3 = Line(a, b);
auto it = hull.lower_bound(l3);
if (it != hull.end() && areParallel(*it, l3)) {
if ((isMax && it->b < b) || (!isMax && it->b > b)) it = hull.erase(it);
else return;
}
it = hull.insert(it, l3);
if (irrelevant(it)) { hull.erase(it); return; }
while (hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it));
while (hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it));
it = updateLeftBorder(it);
if (hasPrev(it)) updateLeftBorder(std::prev(it));
if (hasNext(it)) updateLeftBorder(std::next(it));
}
val_t getBest(coord_t x) const {
Line q;
q.val = x, q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery;
auto bestLine = hull.lower_bound(q);
if (isMax) --bestLine;
return bestLine->valueAt(x);
}
} ziba;
void addLine(ll x,ll v){
ziba.addLine(-v,-x);
}
ll find_min_aT(ll t){
return -ziba.getBest(t);
}
ll h[maxn];
ll w[maxn];
ll c[maxn];
ll dp[maxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,s=0;
cin>>n;
for(ll i=0;i<n;i++){
cin>>h[i];
}
for(ll i=0;i<n;i++){
cin>>w[i];
s+=w[i];
}
for(ll i=0;i<n;i++){
c[i]=-w[i]+h[i]*h[i];
if(0<i && i<n-1){
c[i]+=h[i]*h[i];
}
}
dp[0]=c[0];
addLine(dp[0],-2*h[0]);
for(ll i=1;i<n;i++){
dp[i]=find_min_aT(h[i])+c[i];
addLine(dp[i],-2*h[i]);
}
cout<<dp[n-1]+s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
95 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
96 ms |
4732 KB |
Output is correct |
| 4 |
Correct |
98 ms |
4472 KB |
Output is correct |
| 5 |
Correct |
80 ms |
6904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
95 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
95 ms |
4728 KB |
Output is correct |
| 8 |
Correct |
96 ms |
4732 KB |
Output is correct |
| 9 |
Correct |
98 ms |
4472 KB |
Output is correct |
| 10 |
Correct |
80 ms |
6904 KB |
Output is correct |
| 11 |
Correct |
87 ms |
4764 KB |
Output is correct |
| 12 |
Correct |
99 ms |
4656 KB |
Output is correct |
| 13 |
Correct |
67 ms |
4600 KB |
Output is correct |
| 14 |
Correct |
95 ms |
4856 KB |
Output is correct |
| 15 |
Correct |
133 ms |
16884 KB |
Output is correct |
| 16 |
Correct |
81 ms |
7056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
4600 KB |
Output is correct |
| 18 |
Correct |
23 ms |
4600 KB |
Output is correct |
