Chủ Nhật, 18 tháng 12, 2022

nhahang c++

#include <bits/stdc++.h>
using namespace std;
struct qq
{
    int a,b;
};
int n,p,f[50001],q[50001],l[50001],s=0,k,h,res,res1[50001];
qq c[50001];
void nhap()
{
    cin>>n>>p;
    for (int i=1;i<=n;i++) cin>>c[i].a>>c[i].b;
}
 
bool ss(qq &x,qq &y)
{
    if (x.a<y.a) return true;
    if (x.a>y.a) return false;
    if (x.b<y.b) return true;
    if (x.b>y.b) return false;
    return false;
}
 
void giai()
{
    int maxx,jmax;
    sort(c+1,c+1+n,ss);
    if(c[n].a<p)
    {
        cout<<"0";
        return;
    }
    c[0].a=0;c[0].b=0;f[0]=0;
    for(int i=1;i<=n;i++)
    {
        maxx=-1;
        for(int j=0;j<=i-1;j++)
            if((c[i].a-c[j].a)>=p&&f[j]>maxx)
            {
                maxx=f[j];
                jmax=j;
            }
        if (maxx==-1) f[i]=0;
        else
        {
            f[i]=maxx+c[i].b;
            //t[i]=jmax;
        }
    }
    int res=1;
    for(int i=1;i<=n;i++)
    {
        //cout<<f[i]<<endl;
        if(f[res]<f[i]) res=i;
    }
    cout<<f[res];
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 //   freopen("nhahang.inp","r",stdin);
 //   freopen("nhahang.out","w",stdout);
    nhap();
    giai();
}

Không có nhận xét nào:

Đăng nhận xét

Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.