Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2014
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.62 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. const int MAX=200000;
  4. struct htrick
  5. {
  6. long long a;
  7. long long b;
  8. }s[MAX];
  9. int main()
  10. {
  11. ios_base::sync_with_stdio(0);
  12. cin.tie(0);
  13. long long n,i,h[MAX],c[MAX],p,j;
  14. cin>>n;
  15. for(i=0;i<n;i++)
  16. cin>>h[i];
  17. for(i=0;i<n;i++)
  18. cin>>c[i];
  19. j=p=0;
  20. s[p].a=c[0];
  21. s[p].b=0;
  22. for(i=1;i<n;i++)
  23. {
  24. while(p>j && s[j].a*h[i]+s[j].b>=s[j+1].a*h[i]+s[j+1].b)
  25. j++;
  26. p++;
  27. s[p].a=c[i];
  28. s[p].b=s[j].a*h[i]+s[j].b;
  29. 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))
  30. {
  31. s[p-1]=s[p];
  32. p--;
  33. }
  34. }
  35. cout<<s[p].b<<endl;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement