Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- const int MAX=200000;
- struct htrick
- {
- long long a;
- long long b;
- }s[MAX];
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- long long n,i,h[MAX],c[MAX],p,j;
- cin>>n;
- for(i=0;i<n;i++)
- cin>>h[i];
- for(i=0;i<n;i++)
- cin>>c[i];
- j=p=0;
- s[p].a=c[0];
- s[p].b=0;
- for(i=1;i<n;i++)
- {
- while(p>j && s[j].a*h[i]+s[j].b>=s[j+1].a*h[i]+s[j+1].b)
- j++;
- p++;
- s[p].a=c[i];
- s[p].b=s[j].a*h[i]+s[j].b;
- while(p>1 && (s[p-2].b-s[p].b)*(s[p-1].a-s[p-2].a)<=(s[p-2].b-s[p-1].b)*(s[p].a-s[p-2].a))
- {
- s[p-1]=s[p];
- p--;
- }
- }
- cout<<s[p].b<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement