#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
// maximum cht = type(1), minimum cht = type(-1)
struct cht {
typedef long long ll;
struct line {
ll m, b, i, q;
double nxt = 9e18;
line(ll mm, ll bb, ll ii, ll qq = 0) : m(mm), b(bb), i(ii), q(qq) {};
bool operator < (const line &x) const {
if (!q && !x.q) return m < x.m;
if (q) return m < x.nxt;
return nxt < x.m;
}
};
double cut(const line &x, const line &y) {
return double(x.b - y.b) / (y.m - x.m);
}
int sign, nxtind = 0;
cht(int type) {
sign = type;
}
typedef set<line> s;
s h;
void upd(s::iterator &it) {
if (next(it) != h.end()) {
double n = cut(*it, *next(it));
line l = *it;
h.erase(it);
l.nxt = n;
it = h.insert(l).first;
}
}
bool ok(s::iterator it) {
if (it == h.begin() || next(it) == h.end() || cut(*prev(it), *it) < cut(*it, *next(it))) return true;
return h.erase(it), false;
}
void insert(ll slope, ll constant) {
line add(sign * slope, sign * constant, nxtind++);
s::iterator it = h.insert(add).first;
if (!ok(it)) return;
while (it != h.begin() && !ok(prev(it)));
while (next(it) != h.end() && !ok(next(it)));
upd(it);
if (it != h.begin()) upd(--it);
}
ll query(ll x) {
line l = *h.lower_bound(line(x, 0, 0, 1));
return sign * (x * l.m + l.b);
}
// returns the index of the best slope (indexed by the amount of lines tried to insert prior to it)
ll iquery(ll x) {
return h.lower_bound(line(x, 0, 0, 1))->i;
}
};
int n;
vector<ll> h, w, sw, dp;
cht c(-1);
int main() {
fast;
cin >> n;
h.resize(n);
w.resize(n);
sw.resize(n);
dp.resize(n);
for (auto &i : h) cin >> i;
for (auto &i : w) cin >> i;
sw[0] = w[0];
for (int i = 1; i < n; i++) sw[i] = sw[i - 1] + w[i];
dp[0] = 0;
// cout << "for i " << 0 << " inserted " << dp[0] + h[0] * h[0] - sw[0] << " " << -2 * h[0] << endl;
c.insert(-2 * h[0], dp[0] + h[0] * h[0] - sw[0]);
for (int i = 1; i < n; i++) {
dp[i] = c.query(h[i]) + sw[i - 1] + h[i] * h[i];
// cout << "for i " << i << " inserted " << -2 * h[i] << " " << dp[i] + h[i] * h[i] - sw[i] << endl;
c.insert(-2 * h[i], dp[i] + h[i] * h[i] - sw[i]);
}
// for (int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl;
cout << dp.back() << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
3880 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
3880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
