#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;
// assumes b1, b2 are nonzero
bool smaller(ll t1, ll b1, ll t2, ll b2) {
if (abs((ll)9e18 / b2) < t1 || abs((ll)9e18 / b1) < t2) return (ldb)t1 / b1 < (ldb)t2 / b2;
if ((b1 > 0) == (b2 > 0)) return t1 * b2 < t2 * b1;
return t1 * b2 > t2 * b1;
}
// 1 for maximum, -1 for minimum
struct cht {
struct line {
ll m, b;
bool q;
ll nxtm, nxtb;
line(ll mm = 0, ll bb = 0, bool qq = false) {
m = mm;
b = bb;
q = qq;
nxtm = nxtb = 9e18;
}
bool operator < (const line &x) const {
if (!q && !x.q)
return m < x.m;
if (x.q) {
// cout << "comparison with line " << -m << " " << -b << endl;
if (nxtm == (ll)9e18) return false;
// cout << "has next slope as " << nxtm << endl;
// cout << (ldb)(b - nxtb) / (nxtm - m) << endl;
return smaller(b - nxtb, nxtm - m, x.m, 1);
}
return !(x < *this);
}
};
int sign;
set<line> h;
cht(int type = 1) {
sign = type;
}
void upd(set<line>::iterator &it) {
if (next(it) == h.end()) return;
line l1 = *it, l2 = *next(it);
h.erase(it);
l1.nxtm = l2.m, l1.nxtb = l2.b;
it = h.insert(l1).first;
}
bool ok(set<line>::iterator &it) {
// cout << "h" << endl;
if (it == h.begin() || next(it) == h.end()) return true;
// cout << "hm" << endl;
auto it1 = prev(it), it2 = next(it);
// cout << "hmm" << endl;
bool rtn = smaller(it1->b - it->b, it->m - it1->m, it2->b - it->b, it->m - it2->m);
// cout << "hmmm" << endl;
if (!rtn) {
// cout << "erasing " << sign * it->m << " " << sign * it->b << endl;
h.erase(it);
upd(it1);
it = it1;
// cout << "end erase" << endl;
}
return rtn;
}
void insert(ll constant, ll slope) {
line l(sign * slope, sign * constant);
auto pp = h.insert(l);
set<line>::iterator it, it2;
if (pp.second) it = pp.first;
else {
if (sign * pp.first->b <= sign * l.b) return;
h.erase(pp.first);
it = h.insert(l).first;
}
if (!ok(it)) return;
upd(it);
if (it != h.begin()) upd(--it), ++it;
// debug;
if (it != h.begin()) {
while (!ok(it2 = prev(it)));
}
// debug;
if (next(it) != h.end()) {
while (!ok(it2 = next(it))) it = it2;
}
// debug;
}
ll query(ll x) {
// cout << "looking for optimum on x " << x << endl;
line l(x, 0, true);
auto it = h.lower_bound(l);
// cout << "optimum for x " << x << " is line ";
// cout << sign * it->m << " " << sign * it->b << endl;
return sign * (x * it->m + it->b);
}
};
int n;
vector<ll> h, w, sw, dp;
cht c(-1);
int main() {
fast;
// freopen("C:\\Users\\Noam\\Desktop\\building.01.05.in", "r", stdin);
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(dp[0] + h[0] * h[0] - sw[0], -2 * h[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(dp[i] + h[i] * h[i] - sw[i], -2 * h[i]);
}
// for (int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl;
cout << dp.back() << endl;
/*
vector<ll> dp2(n);
dp2[0] = 0;
for (int i = 1; i < n; i++) {
dp2[i] = 9e18;
for (int j = 0; j < i; j++)
dp2[i] = min(dp2[i], dp2[j] + (h[i] - h[j]) * (h[i] - h[j]) + sw[i - 1] - sw[j]);
}
cout << dp2.back() << endl;
for (int i = 0; i < n; i++) {
if (dp[i] != dp2[i]) {
cout << "first difference at " << i << endl;
cout << dp[i] << " " << dp2[i] << endl;
return 0;
}
}
*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
4 ms |
492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
3732 KB |
Output is correct |
| 2 |
Correct |
157 ms |
3892 KB |
Output is correct |
| 3 |
Correct |
164 ms |
3892 KB |
Output is correct |
| 4 |
Correct |
205 ms |
3892 KB |
Output is correct |
| 5 |
Correct |
183 ms |
5268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
4 ms |
492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
532 KB |
Output is correct |
| 6 |
Correct |
177 ms |
3732 KB |
Output is correct |
| 7 |
Correct |
157 ms |
3892 KB |
Output is correct |
| 8 |
Correct |
164 ms |
3892 KB |
Output is correct |
| 9 |
Correct |
205 ms |
3892 KB |
Output is correct |
| 10 |
Correct |
183 ms |
5268 KB |
Output is correct |
| 11 |
Correct |
142 ms |
5268 KB |
Output is correct |
| 12 |
Correct |
162 ms |
5268 KB |
Output is correct |
| 13 |
Correct |
112 ms |
5268 KB |
Output is correct |
| 14 |
Correct |
172 ms |
5268 KB |
Output is correct |
| 15 |
Correct |
221 ms |
11684 KB |
Output is correct |
| 16 |
Correct |
182 ms |
11684 KB |
Output is correct |
| 17 |
Correct |
30 ms |
11684 KB |
Output is correct |
| 18 |
Correct |
28 ms |
11684 KB |
Output is correct |
