Advertisement
didedoshka

haha precision

Nov 20th, 2020
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <cmath>
  6. #include <set>
  7. #include <stack>
  8. #include <bitset>
  9. #include <map>
  10. #include <ctime>
  11. #include <numeric>
  12. #include <random>
  13.  
  14.  
  15. #ifndef M_PI
  16. #define M_PI 3.1415926535897932384626433832795028841
  17. #endif
  18. #define int long long
  19. #define uint unsigned long long
  20. #define double long double
  21.  
  22. #ifdef TIME
  23. #define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false);int32_t START = clock()
  24. #define finish cout << "\ntime: " << (clock() - START) / (CLOCKS_PER_SEC * 1.0); return 0
  25. #endif
  26.  
  27. #ifndef TIME
  28. #define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
  29. #define finish return 0
  30. #endif
  31.  
  32. using namespace std;
  33.  
  34.  
  35. //vector input
  36. template<typename T>
  37. istream &operator>>(istream &is, vector<T> &vec) {
  38.     for (auto &i : vec) {
  39.         cin >> i;
  40.     }
  41.     return is;
  42. }
  43.  
  44. //pair output
  45. template<typename E>
  46. ostream &operator<<(ostream &os, pair<E, E> &t) {
  47.     os << t.first << ' ' << t.second;
  48.     return os;
  49. }
  50.  
  51. //"map" pair output
  52. template<typename E>
  53. ostream &operator<<(ostream &os, pair<const E, E> &t) {
  54.     os << t.first << ' ' << t.second;
  55.     return os;
  56. }
  57.  
  58. //vector output
  59. template<typename T>
  60. ostream &operator<<(ostream &os, vector<T> &vec) {
  61.     for (T i : vec) {
  62.         os << i << ' ';
  63.     }
  64.     return os;
  65. }
  66.  
  67. //2 dimensional vector output
  68. template<typename T>
  69. ostream &operator<<(ostream &os, vector<vector<T> > &vec) {
  70.     for (vector<T> i : vec) {
  71.         os << i << '\n';
  72.     }
  73.     return os;
  74. }
  75.  
  76. struct segtree {
  77.     int n;
  78.     vector<double> tree;
  79.  
  80.     segtree(int _n) {
  81.         n = _n;
  82.         tree.resize(2 * n);
  83.     }
  84.  
  85.     void set(int i, double v) {
  86.         i += n;
  87.         tree[i] = v;
  88.         i /= 2;
  89.         while (i != 0) {
  90.             tree[i] = max(tree[2 * i], tree[2 * i + 1]);
  91.             i /= 2;
  92.         }
  93.     }
  94.  
  95.     double get(int l, int r) {
  96.         l += n;
  97.         r += n;
  98.         double ans = 0;
  99.         while (l <= r) {
  100.             if (l % 2 == 1) {
  101.                 ans = max(ans, tree[l]);
  102.                 l += 1;
  103.             }
  104.             if (r % 2 == 0) {
  105.                 ans = max(ans, tree[r]);
  106.                 r -= 1;
  107.             }
  108.             l /= 2;
  109.             r /= 2;
  110.         }
  111.         return ans;
  112.     }
  113. };
  114.  
  115. int32_t main() {
  116.     start;
  117.  
  118.     int n;
  119.     cin >> n;
  120.     vector<pair<int, int>> a(n);
  121.     vector<double> v(n);
  122.     vector<int> vv(n);
  123.     vector<double> c(n);
  124.     for (int i = 0; i < n; ++i) {
  125.         cin >> a[i].first >> a[i].second;
  126.         v[i] = M_PI * ((double)a[i].first * (double)a[i].first) * (double)a[i].second;
  127.     }
  128.     c = v;
  129.     sort(c.begin(), c.end());
  130.     c.resize(distance(c.begin(), unique(c.begin(), c.end())));
  131.     for (int i = 0; i < n; ++i) {
  132.         vv[i] = distance(c.begin(), lower_bound(c.begin(), c.end(), v[i]));
  133.     }
  134.  
  135.     vector<double> dp(n, 0);
  136.  
  137.     segtree sgt((int)c.size() + 1);
  138.  
  139.     for (int i = 0; i < n; ++i) {
  140.         dp[i] = sgt.get(0, vv[i] - 1) + v[i];
  141.         sgt.set(vv[i], dp[i]);
  142.     }
  143.  
  144.  
  145.     cout << *max_element(dp.begin(), dp.end()) << '\n';
  146.  
  147.  
  148.     finish;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement