//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n;
vector<ll> w , h;
ll dp[100000] , inf[100000][2];
set<arr(2)> pt;
arr(2) dd = {-1 , -1};
void init(){
for(int i = 1 ; i < n ; i++) w[i] += w[i - 1];
for(int i = 0 ; i < n ; i++){
inf[i][1] = (h[i] * h[i]) , inf[i][0] = (h[i] * h[i]) - w[i];
if(i > 0) inf[i][1] += w[i - 1];
}
}
int bsMx(int i){
int l = 0 , r = int(1e6) + 1;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
dd[0] = c;
int inx = (*(--pt.ub(dd)))[1];
if(h[inx] < h[i]) l = c - 1;
else{
if(dp[inx] - ((2ll * c) * h[inx]) < dp[i] - ((2ll * c) * h[i])) r = c;
else l = c - 1;
}
}
if(r - l - 1 == 1){
dd[0] = l + 1;
int inx = (*(--pt.ub(dd)))[1];
if(h[inx] < h[i]) return l + 1;
else if(dp[inx] - ((2ll * (l + 1)) * h[inx]) >= dp[i] - ((2ll * (l + 1)) * h[i])) return l + 1;
}
return l;
}
int bsMn(int i , int r){
int l = -1;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
dd[0] = c;
int inx = (*(--pt.ub(dd)))[1];
if(dp[i] - ((2ll * c) * h[i]) < dp[inx] - ((2ll * c) * h[inx])) r = c;
else l = c - 1;
}
if(r - l - 1 == 1){
dd[0] = r - 1;
int inx = (*(--pt.ub(dd)))[1];
if(dp[i] - ((2ll * (r - 1)) * h[i]) < dp[inx] - ((2ll * (r - 1)) * h[inx])) return r - 1;
}
return r;
}
void addEl(int i){
if(pt.empty()){
pt.insert({0 , i});
return;
}
int r = bsMx(i);
int l = bsMn(i , r + 1);
if(l > r) return;
dd[0] = l;
auto itr1 = pt.lb(dd);
dd[0] = r;
auto itr2 = pt.ub(dd);
if(itr1 == itr2){
pt.insert({l , i});
return;
}
vector<arr(2)> dls , adds;
itr2--;
while(true){
dls.pb((*itr1));
if(itr2 == itr1){
adds.pb({r + 1 , (*itr2)[1]});
if((*++itr1)[0] == r + 1) adds.cl();
break;
}
itr1++;
}
pt.insert({l , i});
for(auto &el : dls) pt.erase(el);
for(auto &el : adds) pt.insert(el);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
h.pb(0);
cin >> h.back();
}
for(int i = 0 ; i < n ; i++){
w.pb(0);
cin >> w.back();
}
init();
dp[n - 1] += inf[n - 1][1];
addEl(n - 1);
for(int i = n - 2 ; i >= 0 ; i--){
dd[0] = h[i];
int inx = (*(--pt.ub(dd)))[1];
dp[i] = dp[inx] + inf[i][0] - ((2ll * h[i]) * (1ll * h[inx]));
if(i > 0) dp[i] += inf[i][1];
addEl(i);
}
cout << dp[0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
297 ms |
5412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
