CodeForce-799C Fountains (记忆化DP)

Fountains

CodeForces - 799C

某土豪想要造两座喷泉。现在有 n 个造喷泉的方案，我们已知每个方案的价格以及美观度。有两种合法的货币：金币和钻石。这两种货币之间不能以任何方式转换。

找出一种合法方案使得两座喷泉的美观度和最大。

Input

第一行包含 3 个整数 n, c 和 d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — 表示造喷泉的方案数，金币的数量和钻石的数量。

之后 n 行描述每一种建造喷泉的方案。每行包含两个整数 b_i 和 p_i (1 ≤ b_i, p_i ≤ 100 000) — 分别表示第 i 个喷泉的美观度和价格，之后一个字符"C" 或 "D"，表示这个价格使用金币还是钻石描述的。

Output

输出两个美观度最大的喷泉的美观度和。如果没有合法方案，输出 0.

Example

Input

Output

Input

2 4 5
2 5 C
2 1 D

Output

Input

Output

Note

第一个样例中造第2个喷泉，美观度为 4, 价格为 3 金币。第一个喷泉没有足够的金币来造。同时还造第3个喷泉，美观度为 5 ，价格为 6 钻石。那么总美观度为 9。

第二个样例中没有合法方案。

可以预处理出

pre1[N][2]

表示花费N个金币,能够获得的最大美丽值和次小美丽值;

然后对以下3种情况枚举其中的一个;

一.

两个商品都是金币买的

则枚举其中一个商品是哪一个;

然后看看余额还剩多少->rest;

直接获取pre1[rest][0]

如果枚举的商品的价格<=rest且pre1[rest][0]和这个枚举的商品的美丽值一样

就取pre1[rest][1];即次小值;

二.

两个商品都是钻石买的，同上

三.

一个商品是钻石买的，另外一个是金币买的，各自单独找最大值；

#include <bits/stdc++.h>

#define rep1(i,x,y) for(int i=x;i<=y;i++)

#define rep2(i,x,y) for(int i=y;i>=x;i--)

#define pb push_back

#define long long ll

using namespace std;

const int N=2e5+100;

struct node

{

    int b;//beauty

    int p;//price

    int id;

};

vector<int> g[2][N];//the beauty of two types fountain from each price

int bo[2][N][2];

int n,c,d;

node a[N];

int main()

{

    ios_base::sync_with_stdio(0);

    cin>>n>>c>>d;

    char s[3];

    rep1(i,1,n)

    {

        cin>>a[i].b>>a[i].p;

        cin>>s;

        a[i].id=(s[0]=='C') ? 0:1;

        g[a[i].id][a[i].p].pb(a[i].b);

    }

    rep1(k,0,1)

    {

        rep1(i,1,100000)

        {

            bo[k][i][1]=bo[k][i-1][1];//DP

            bo[k][i][0]=bo[k][i-1][0];//DP

            int len=g[k][i].size();

            rep1(j,0,len-1)

            {

                if(g[k][i][j]>bo[k][i][0])

                {//g[k(*id)][i(*price)][j(*beauty)]

                    bo[k][i][1]=bo[k][i][0];

                    bo[k][i][0]=g[k][i][j];

                    //bo[k][i][0] find the best beauty and

                    //bo[k][i][0] the second beauty

                    //of fountains in the same price by coins

                    //(or diamonds,depends on "k")

                }

                else if(g[k][i][j]>bo[k][i][1])

                    bo[k][i][1]=g[k][i][j];

            }

        }

    }

    //all coins

    int ans=0;

     rep1(i,1,n)

        if (a[i].id==0)

        {

            int t1 = a[i].b,t2 = a[i].p;

            int rest = c-t2;

            if (rest<=0) continue;

            int t3 = bo[0][rest][0];

            if (t2<=rest && t1==t3)

                t3 = bo[0][rest][1];

            if (t3<=0) continue;

            ans = max(ans,t1+t3);

        }

    //all diamonds

     rep1(i,1,n)

        if (a[i].id==1)

        {

            int t1 = a[i].b,t2 = a[i].p;

            int rest = d-t2;

            if (rest<=0) continue;

            int t3 = bo[1][rest][0];

            if (t2<=rest && t1==t3)

                t3 = bo[1][rest][1];

            if (t3<=0) continue;

            ans = max(ans,t1+t3);

        }

    //half coin half diamond

    rep1(i,1,n)

        {

            int t1 = a[i].b,t2 = a[i].p;

            int rest,t3;

            if (a[i].id==0)

            {

                rest = d;

                if (t2>c) continue;

            }

            else

            {

                rest = c;

                if (t2>d) continue;

            }

            if (rest<=0)  continue;

            t3 = bo[1-a[i].id][rest][0];

            if (t3<=0) continue;

            ans = max(ans,t1+t3);

        }

    cout<<ans<<endl;

    return 0;

}

巴特西

CodeForce-799C Fountains (记忆化DP)

Fountains

最新文章

热门文章