/***
* ___ ___ ___ ___
* /\__\ /\ \ /\__\ /\__\
* /:| _|_ _\:\ \ /:/ _/_ /::L_L_
* /::|/\__\ /\/::\__\ /:/_/\__\ /:/L:\__\
* \/|::/ / \::/\/__/ \:\/:/ / \/_/:/ /
* |:/ / \:\__\ \::/ / /:/ /
* \/__/ \/__/ \/__/ \/__/
*/
#define task ""
#include <bits/stdc++.h>
/** **/
typedef long long ll;
typedef long double db;
using namespace std;
/** **/
#define int long long
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pll pair<ll,ll>
#define ALL(x) x.begin(),x.end()
#define len(s) ((int)(s.size()))
#define mask(i) (1LL<<(i))
#define bit(i,j) ((1LL<<(j))&(i))
#define on(i,j) ((1LL<<(j))|(i))
#define off(i,j) ((~(1LL<<(j)))&(i))
#define FOR(i,a,b) for(ll i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(ll i = (a); i >= (b); --i)
/** **/
int N;
#define MAXN 100005
int h[MAXN];
int w[MAXN];
int pref[MAXN];
const int INF = 1e18;
struct line{
int a, b;
line() : a(0), b(0) {};
line(const int &a, const int &b): a(a), b(b) {};
int value(const int &x) {return a * x + b;};
int slope() {return a;};
};
struct LCTopt{
int n;
vector<line> st;
LCTopt(const int &_size) : n(_size), st(_size + 1, line(0, INF)) {};
void update(int l, int r, line F){
if (l > r) return;
int mid = (l + r) >> 1;
if (l == r) return st[mid] = (F.value(l) < st[mid].value(l) ? F : st[mid]), void();
if (st[mid].value(mid) > F.value(mid)) swap(st[mid], F);
if (F.value(l) < st[mid].value(l)) update(l, mid - 1, F);
if (F.value(r) < st[mid].value(r)) update(mid + 1, r, F);
}
void update(line F){ return update(1, n, F); };
int query(int l, int r, int p){
int mid = (l + r) >> 1;
int value = st[mid].value(p);
if (p == mid) return value;
if (p < mid) return min(query(l, mid - 1, p), value);
return min(query(mid + 1, r, p), value);
}
int query(int p) {return query(1, n, p);};
};
/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/
void solve(){
cin >> N;
int MAX = 0;
FOR(i,1,N) cin >> h[i];
FOR(i,1,N) MAX = max(MAX, h[i]);
FOR(i,1,N) cin >> w[i];
FOR(i,1,N) pref[i]=pref[i-1]+w[i];
LCTopt tree(MAX);
tree.update(line(-2*h[1], h[1]*h[1]));
FOR(i,2,N){
int dpi = tree.query(h[i]) + pref[i-1] + h[i]*h[i];
if (i == N) return cout << dpi, void();
tree.update(line(-2*h[i], h[i]*h[i] + dpi - pref[i]));
}
}
/** **/
int32_t main(){
if (fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}
Compilation message
building.cpp: In function 'int32_t main()':
building.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
5456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
