#include <bits/stdc++.h>
#define INF 100000000000000000.0
using namespace std;
typedef long long ll;
struct Line {
ll a, b; // Y = aX + b
double kp, vp;
Line() {}
Line(ll aa, ll bb) {
a = aa;
b = bb;
}
const bool operator< (Line masik) const {
if(a != masik.a) return a > masik.a;
return b < masik.b;
}
};
double cross(Line e, Line f) {
return (double)(f.b - e.b) / (double)(e.a - f.a);
}
struct Burok {
vector<Line> tab;
bool ord;
Burok() {
tab.resize(0);
ord = false;
}
void Add_Line(ll a, ll b) {
ord = false;
Line uj(a,b);
tab.push_back(uj);
}
void Order() {
ord = true;
sort(tab.begin(),tab.end());
if(tab.size()==1) return;
vector<Line> ch(tab.size());
ch[0] = tab[0];
ll it = 1; while(it < tab.size() && ch[0].a == tab[it].a) { it++; };
if(it >= tab.size()) {
ch.resize(1);
swap(tab,ch); return;
}
ch[1] = tab[it]; it++;
ll hm = 1;
for(;it<tab.size();it++) {
if(tab[it].a == ch[hm].a) continue;
bool kell = true;
while(hm >= 1 && kell) {
double ez = cross(ch[hm-1],tab[it]);
double az = cross(ch[hm-1],ch[hm]);
if(ez <= az) { //!!!!!!
hm--;
}
else {
kell = false;
}
}
ch[hm+1] = tab[it]; hm++;
}
ch.resize(hm+1);
swap(tab,ch);
for(ll i=0;i<tab.size()-1;i++) {
tab[i].vp = cross(tab[i],tab[i+1]);
tab[i+1].kp = cross(tab[i+1],tab[i]);
}
tab[0].kp = -INF;
tab[hm].vp = INF;
return;
}
ll Get_Min_Value(ll x) {
if(tab.size() == 0) return (ll)INF;
if(!ord) {
ll min_val(tab[0].a * x + tab[0].b);
for(Line d:tab) {
min_val = min(min_val,d.a * x + d.b);
}
return min_val;
}
else {
ll b1 = 0;
ll b2 = tab.size()-1;
while(b1 < b2) {
ll mid = (b1 + b2) / 2;
if(tab[mid].kp <= (double)x && (double)x <=tab[mid].vp) {
b1 = mid;
b2 = mid;
}
else if(tab[mid].kp > (double)x) {
b2 = mid-1;
}
else {
b1 = mid+1;
}
}
return x * tab[b1].a + tab[b1].b;
}
}
};
ll n;
const ll maxn = 100005;
ll h[maxn], w[maxn];
Burok data[400];
ll suf_sum[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(ll i=0;i<n;i++) {
cin>>h[i];
}
for(ll i=0;i<n;i++) {
cin>>w[i];
}
suf_sum[n] = 0;
for(ll i=n-1;i>=0;i--) {
suf_sum[i] = suf_sum[i+1] + w[i];
}
ll g = (ll)sqrt(n);
for(ll i=0;i<n;i++) {
if(i == 0) {
data[i/g].Add_Line(-2*h[i],h[i]*h[i] + suf_sum[i+1]);
}
else {
ll min_pre_cost = (ll) INF;
for(ll j=0;j<=i/g;j++) {
min_pre_cost = min(min_pre_cost, data[j].Get_Min_Value(h[i]));
}
ll cost = min_pre_cost + h[i]*h[i] - suf_sum[i];
if(i == n-1) {
cout<<cost<<endl;
return 0;
}
data[i/g].Add_Line(-2*h[i],cost + suf_sum[i+1] + h[i]*h[i]);
}
if((i+1) % g == 0) {
data[i/g].Order();
}
}
return 0;
}
Compilation message
building.cpp: In member function 'void Burok::Order()':
building.cpp:43:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
ll it = 1; while(it < tab.size() && ch[0].a == tab[it].a) { it++; };
~~~^~~~~~~~~~~~
building.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it >= tab.size()) {
~~~^~~~~~~~~~~~~
building.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;it<tab.size();it++) {
~~^~~~~~~~~~~
building.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i<tab.size()-1;i++) {
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
720 KB |
Output is correct |
| 5 |
Correct |
4 ms |
764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1491 ms |
7312 KB |
Output is correct |
| 2 |
Correct |
1463 ms |
8272 KB |
Output is correct |
| 3 |
Correct |
1367 ms |
9408 KB |
Output is correct |
| 4 |
Correct |
1330 ms |
10304 KB |
Output is correct |
| 5 |
Correct |
572 ms |
11244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
720 KB |
Output is correct |
| 5 |
Correct |
4 ms |
764 KB |
Output is correct |
| 6 |
Correct |
1491 ms |
7312 KB |
Output is correct |
| 7 |
Correct |
1463 ms |
8272 KB |
Output is correct |
| 8 |
Correct |
1367 ms |
9408 KB |
Output is correct |
| 9 |
Correct |
1330 ms |
10304 KB |
Output is correct |
| 10 |
Correct |
572 ms |
11244 KB |
Output is correct |
| 11 |
Correct |
1184 ms |
12460 KB |
Output is correct |
| 12 |
Correct |
1402 ms |
13488 KB |
Output is correct |
| 13 |
Correct |
443 ms |
14716 KB |
Output is correct |
| 14 |
Correct |
1383 ms |
15856 KB |
Output is correct |
| 15 |
Correct |
609 ms |
16748 KB |
Output is correct |
| 16 |
Correct |
519 ms |
17488 KB |
Output is correct |
| 17 |
Correct |
105 ms |
18532 KB |
Output is correct |
| 18 |
Correct |
173 ms |
19776 KB |
Output is correct |
