【20.19%】【codeforces 629D】Babaei and Birthday Cake

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party’s cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

Output

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let’s assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Examples

input

2

100 30

40 10

output

942477.796077000

input

4

1 1

9 7

1 4

10 7

output

3983.539484752

Note

In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

【题解】



DP

设f[i]表示以i号蛋糕作为最上面一层能获取到的最大体积；

f[i] = max(f[j])+v[i];(1<=j<=i-1);

其中j要满足v[j]小于v[i]

(不能等于!)

这样做肯定是O(N^2),而N最大10W。。

考虑到我们需要1..i-1里面小于v[i]且f最大的f值；

则我们考虑用线段树来维护；

这里需要先把数据离散化一下(离散化的标准以r^2*h就好，pi作为一个常数不用乘进去);

然后用lower_bound什么的获取每个数据新的key值；

key值小的对应的数据就小;

则我们顺序处理保证了i小于j;

然后在1..key[i]-1里面找f最大的值；

这里另外一层含义就是说把体积当下标来使用；

f[体积]表示以这个体积作为最上面一层的蛋糕的最大体积;

这里线段树就维护了f[1..当前体积-1]里的最大值,并快速检索；

当然在计算体积的时候要把pi乘进去；

当然你也可以选择加完之后输出答案的时候再乘；

whatever.

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

#define lson L,m,rt<<1

#define rson m+1,R,rt<<1|1

#define LL long long

using namespace std;

const int MAXN = 2e5;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {0,0,0,-1,1};

const double pi = acos(-1.0);

int n,key[MAXN];

LL v[MAXN],r[MAXN],h[MAXN];

double maxsum[MAXN<<2];

vector <LL> a;

void input_LL(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)) t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void input_int(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)) t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void build(int L,int R,int rt)

{

    maxsum[rt] = 0;

    int m = (L+R)>>1;

    if (L==R)

        return;

    build(lson);

    build(rson);

}

double query(int l,int r,int L,int R,int rt)

{

    if (l>r)

        return 0;

    if (l <= L && R <= r)

        return maxsum[rt];

    int m = (L+R)>>1;

    double res = 0;

    if (l <= m)

        res = max(res,query(l,r,lson));

    if (m < r)

        res = max(res,query(l,r,rson));

    return res;

}

void up_data(int pos,double ke,int L,int R,int rt)

{

    if (L==R)

    {

        maxsum[rt] = max(maxsum[rt],ke);

        return;

    }

    int m = (L+R)>>1;

    if (pos<=m)

        up_data(pos,ke,lson);

    else

        up_data(pos,ke,rson);

    maxsum[rt] = max(maxsum[rt<<1],maxsum[rt<<1|1]);

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    input_int(n);

    for (int i = 1;i <= n;i++)

    {

        scanf("%d%d",&r[i],&h[i]);

        v[i] =r[i]*r[i]*h[i];

        a.push_back(v[i]);

    }

    sort(a.begin(),a.end());

    for (int i = 1;i <= n;i++)

        key[i] = lower_bound(a.begin(),a.end(),v[i])-a.begin()+1;

    build(1,n,1);

    for (int i = 1;i <= n;i++)

    {

        double vo = pi*r[i]*r[i]*h[i];

        vo += query(1,key[i]-1,1,n,1);

        up_data(key[i],vo,1,n,1);

    }

    printf("%.10lf\n",query(1,n,1,n,1));

    return 0;

}