#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;
inline void fileIO(string s) {
// freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;
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;
int n;
long double h[N], psum[N], w[N], dp[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i , 0 , n)
cin >> h[i];
rep(i , 0 , n) {
cin >> w[i];
psum[i] = w[i];
if (i) psum[i] += psum[i - 1];
}
ziba.addLine(2 * h[0] , -(dp[0] - psum[0] + h[0] * h[0]));
rep(i ,1 ,n) {
dp[i] = -(ziba.getBest(h[i]) - ( psum[i - 1] + h[i] * h[i]));
ziba.addLine(2 * h[i] , -(dp[i] - psum[i] + h[i] * h[i]));
}
cout << (ll)dp[n - 1] << endl;
return 0;
}
| # |
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 |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
6912 KB |
Output is correct |
| 2 |
Correct |
133 ms |
7256 KB |
Output is correct |
| 3 |
Correct |
130 ms |
7276 KB |
Output is correct |
| 4 |
Correct |
127 ms |
7016 KB |
Output is correct |
| 5 |
Correct |
116 ms |
9464 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 |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| 6 |
Correct |
148 ms |
6912 KB |
Output is correct |
| 7 |
Correct |
133 ms |
7256 KB |
Output is correct |
| 8 |
Correct |
130 ms |
7276 KB |
Output is correct |
| 9 |
Correct |
127 ms |
7016 KB |
Output is correct |
| 10 |
Correct |
116 ms |
9464 KB |
Output is correct |
| 11 |
Correct |
124 ms |
7036 KB |
Output is correct |
| 12 |
Correct |
131 ms |
7160 KB |
Output is correct |
| 13 |
Correct |
110 ms |
7032 KB |
Output is correct |
| 14 |
Correct |
126 ms |
7160 KB |
Output is correct |
| 15 |
Correct |
155 ms |
19524 KB |
Output is correct |
| 16 |
Correct |
111 ms |
9448 KB |
Output is correct |
| 17 |
Correct |
50 ms |
7032 KB |
Output is correct |
| 18 |
Correct |
49 ms |
7036 KB |
Output is correct |
