//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define pii pair<int, int>
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(s) (int)((s).size())
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> (i)) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}
const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 1e5 + 1, M = 6;
/*
/\_/\
(= ._.)
/ >? \>$
*/
int n;
int w[N], h[N];
ll dp[N], pre[N];
ll SQR(ll x){
return x*x;
}
bool flag = 0;
#define it multiset<line>::iterator
struct line{
ll m, b;
mutable double p;
line(ll _m, ll _b, double _p){
m = _m, b = _b, p = _p;
}
bool operator < (const line &x) const{
if(!flag){
if(m == x.m) return b < x.b;
return m > x.m;
}
return p < x.p;
}
};
struct linecontainer:multiset<line,less<>>{
const double inf = 1/.0;
bool intersect(it x, it y){
if(y == end()){
x->p = inf;
return false;
}
if(x->m == y->m)
return true;
x->p = 1.0*(x->b - y->b) / (y->m - x->m);
return x->p >= y->p;
}
void add(ll m, ll b){
it z = insert({m,b,0});
it y = z++;
it x = y;
while(intersect(y, z)) intersect(y, z = erase(z));
while((x = y) != begin() && intersect(--x, y)) intersect(x, y = erase(y));
while((y = x) != begin() && intersect(--x, y)) intersect(x, y = erase(y));
}
ll query(ll x){
flag = 1;
line tmp = *lower_bound({0,0,x});
flag = 0;
return tmp.m * x + tmp.b;
}
}hull;
void sol(){
cin >> n;
FOR(i, 1, n) cin >> h[i];
FOR(i, 1, n){
cin >> w[i];
pre[i] = pre[i-1] + w[i];
}
memset(dp, 0x3f, (n+1)*sizeof(ll));
dp[1] = 0;
hull.add(-2*h[1], SQR(h[1]) - w[1]);
FOR(i, 2, n){
dp[i] = hull.query(h[i]) + pre[i-1] + SQR(h[i]);
hull.add(-2*h[i], SQR(h[i]) - pre[i] + dp[i]);
}
// FOR(i, 1, n) cout << dp[i] << endl;
cout << dp[n] << '\n';
}
signed main(){
#define TASK "nhap"
if(fopen(TASK".inp", "r")){
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
fast; int t = 1;
// cin >> t;
while(t--) sol();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}
Compilation message
building.cpp: In member function 'long long int linecontainer::query(long long int)':
building.cpp:99:38: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
99 | line tmp = *lower_bound({0,0,x});
| ^
building.cpp: In function 'int main()':
building.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
3128 KB |
Output is correct |
| 2 |
Correct |
33 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
33 ms |
3676 KB |
Output is correct |
| 4 |
Correct |
31 ms |
3676 KB |
Output is correct |
| 5 |
Correct |
28 ms |
4960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
36 ms |
3128 KB |
Output is correct |
| 7 |
Correct |
33 ms |
3676 KB |
Output is correct |
| 8 |
Correct |
33 ms |
3676 KB |
Output is correct |
| 9 |
Correct |
31 ms |
3676 KB |
Output is correct |
| 10 |
Correct |
28 ms |
4960 KB |
Output is correct |
| 11 |
Correct |
31 ms |
3932 KB |
Output is correct |
| 12 |
Correct |
41 ms |
3868 KB |
Output is correct |
| 13 |
Correct |
25 ms |
3676 KB |
Output is correct |
| 14 |
Correct |
36 ms |
3932 KB |
Output is correct |
| 15 |
Correct |
44 ms |
9808 KB |
Output is correct |
| 16 |
Correct |
27 ms |
4944 KB |
Output is correct |
| 17 |
Correct |
16 ms |
3676 KB |
Output is correct |
| 18 |
Correct |
17 ms |
3828 KB |
Output is correct |
