// ----------------------- TEMPLATE NO.4 ---------------------------
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int N = 1e5 + 100;
const int MX = 1e6 + 5;
const ll oo = 1e16;
// loops
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ROF(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
// others :>
#define nl '\n'
//----------------------------------SOLUTION-----------------------------------//
int n;
ll w[N], h[N], dp[N], pre[N];
struct line{
ll a, b;
line() : a(0), b(0) {}
line(ll a, ll b) : a(a), b(b) {}
ll calc(ll x){
return a * x + b;
}
ll slope() { return a; }
} f[4 * MX];
#define mid ((lx + rx) / 2)
void update(int idx, int lx, int rx, line x){
if(lx == rx){
f[idx] = (x.calc(lx) < f[idx].calc(lx) ? x : f[idx]);
return;
}
if(f[idx].calc(mid) > x.calc(mid)) swap(x, f[idx]);
if(f[idx].slope() < x.slope())
update(idx<<1, lx, mid, x);
if(f[idx].slope() > x.slope())
update(idx<<1|1, mid+1, rx, x);
}
ll query(int idx, int lx, int rx, int p){
ll cur = f[idx].calc(p);
if(lx == rx) return cur;
if(p <= mid)
return min(cur, query(idx<<1, lx, mid, p));
else
return min(cur, query(idx<<1|1, mid+1, rx, p));
}
ll sqr(ll x){
return x * x;
}
void solve(){
cin >> n;
FOR(i, 1, n) cin >> h[i];
FOR(i, 1, n) cin >> w[i];
FOR(i, 1, n) pre[i] = pre[i-1] + w[i];
FOR(i, 1, 4 * MX) f[i] = line(0, oo);
update(1, 0, MX, line(-2 * h[1], sqr(h[1]) - pre[1]) );
FOR(i, 2, n){
dp[i] = query(1, 0, MX, h[i]) + sqr(h[i]) + pre[i-1];
update(1, 0, MX, line(-2 * h[i], dp[i] + sqr(h[i]) - pre[i]));
}
cout << dp[n];
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Wayzz "name"
if (fopen (Wayzz".inp", "r")) {
freopen (Wayzz".inp", "r", stdin);
freopen (Wayzz".out", "w", stdout);
}
int T = 1;
while(T--) solve();
cerr <<"\nTime Elapse: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | freopen (Wayzz".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | freopen (Wayzz".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp: In function 'void solve()':
building.cpp:70:25: warning: iteration 4000019 invokes undefined behavior [-Waggressive-loop-optimizations]
70 | FOR(i, 1, 4 * MX) f[i] = line(0, oo);
| ~~~~~^~~~~~~~~~~~~
building.cpp:12:52: note: within this loop
12 | #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
| ^
building.cpp:70:2: note: in expansion of macro 'FOR'
70 | FOR(i, 1, 4 * MX) f[i] = line(0, oo);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
64080 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
64112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
66068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
64080 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
64112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
