Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- #include <cmath>
- #include <set>
- #include <stack>
- #include <bitset>
- #include <map>
- #include <ctime>
- #include <numeric>
- #include <random>
- #ifndef M_PI
- #define M_PI 3.1415926535897932384626433832795028841
- #endif
- #define int long long
- #define uint unsigned long long
- #define double long double
- #ifdef TIME
- #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()
- #define finish cout << "\ntime: " << (clock() - START) / (CLOCKS_PER_SEC * 1.0); return 0
- #endif
- #ifndef TIME
- #define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
- #define finish return 0
- #endif
- using namespace std;
- //vector input
- template<typename T>
- istream &operator>>(istream &is, vector<T> &vec) {
- for (auto &i : vec) {
- cin >> i;
- }
- return is;
- }
- //pair output
- template<typename E>
- ostream &operator<<(ostream &os, pair<E, E> &t) {
- os << t.first << ' ' << t.second;
- return os;
- }
- //"map" pair output
- template<typename E>
- ostream &operator<<(ostream &os, pair<const E, E> &t) {
- os << t.first << ' ' << t.second;
- return os;
- }
- //vector output
- template<typename T>
- ostream &operator<<(ostream &os, vector<T> &vec) {
- for (T i : vec) {
- os << i << ' ';
- }
- return os;
- }
- //2 dimensional vector output
- template<typename T>
- ostream &operator<<(ostream &os, vector<vector<T> > &vec) {
- for (vector<T> i : vec) {
- os << i << '\n';
- }
- return os;
- }
- struct segtree {
- int n;
- vector<double> tree;
- segtree(int _n) {
- n = _n;
- tree.resize(2 * n);
- }
- void set(int i, double v) {
- i += n;
- tree[i] = v;
- i /= 2;
- while (i != 0) {
- tree[i] = max(tree[2 * i], tree[2 * i + 1]);
- i /= 2;
- }
- }
- double get(int l, int r) {
- l += n;
- r += n;
- double ans = 0;
- while (l <= r) {
- if (l % 2 == 1) {
- ans = max(ans, tree[l]);
- l += 1;
- }
- if (r % 2 == 0) {
- ans = max(ans, tree[r]);
- r -= 1;
- }
- l /= 2;
- r /= 2;
- }
- return ans;
- }
- };
- int32_t main() {
- start;
- int n;
- cin >> n;
- vector<pair<int, int>> a(n);
- vector<double> v(n);
- vector<int> vv(n);
- vector<double> c(n);
- for (int i = 0; i < n; ++i) {
- cin >> a[i].first >> a[i].second;
- v[i] = M_PI * ((double)a[i].first * (double)a[i].first) * (double)a[i].second;
- }
- c = v;
- sort(c.begin(), c.end());
- c.resize(distance(c.begin(), unique(c.begin(), c.end())));
- for (int i = 0; i < n; ++i) {
- vv[i] = distance(c.begin(), lower_bound(c.begin(), c.end(), v[i]));
- }
- vector<double> dp(n, 0);
- segtree sgt((int)c.size() + 1);
- for (int i = 0; i < n; ++i) {
- dp[i] = sgt.get(0, vv[i] - 1) + v[i];
- sgt.set(vv[i], dp[i]);
- }
- cout << *max_element(dp.begin(), dp.end()) << '\n';
- finish;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement