fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define double long double
  4. double tree[100009]={0.0};
  5. #define PI acos(-1)
  6. int n;
  7. vector<double> v,p;
  8. void update(int idx,double val)
  9. {
  10. for(;idx<=100006;idx+=idx&-idx)
  11. tree[idx]=max(tree[idx],val);
  12. }
  13. double read(int idx)
  14. {
  15. double s=0;
  16. for(;idx>0;idx-=idx&-idx)s=max(s,tree[idx]);
  17. return s;
  18. }
  19. int main()
  20. {
  21. cin>>n;
  22. v.push_back(-1.0);
  23. p.push_back(-1.0);
  24. for(int i=1;i<=n;i++)
  25. {
  26. long long r,h;
  27. cin>>r>>h;
  28. v.push_back((double)h*r*r*PI);
  29. p.push_back((double)h*r*r*PI);
  30. }
  31. //v.push_back(-1.0);
  32. sort(v.begin(),v.end());
  33. for(int i=1;i<=n;i++)
  34. {
  35. int t=(int)(upper_bound(v.begin(),v.end(),p[i])-v.begin());
  36. double a=read(t-1)+p[i];
  37. update(t,a);
  38. }
  39. double ans=0.0;
  40. for(int i=1;i<=100006;i++)
  41. ans=max(ans,read(i));
  42. printf("%0.14Lf\n",ans);
  43. return 0;
  44. }
Success #stdin #stdout 0.02s 4640KB
stdin
2
100 30
40 10
stdout
942477.79607693793480