Light OJ 1017 Brush (III)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll arr[1009],dp[1009][1009];

ll n,l;

ll solve(ll pos,ll lft)

{

    ll i;

    if(pos>=n||lft<=0)

        return 0;

    if(dp[pos][lft]!=-1)

        return dp[pos][lft];

    ll bnd=arr[pos]+l;

    ll cnt=0;

    for(i=pos;i<n;i++)

    {

        if(arr[i]<=bnd)

        {

            cnt++;

        }

        else

        {

            break;

        }

    }

    return dp[pos][lft]=max(cnt+solve(i,lft-1),solve(pos+1,lft));

}

int main()

{

    ll i,j,k,m,test,x;

    cin>>test;

    for(k=1;k<=test;k++)

    {

        memset(dp,-1,sizeof(dp));

        cin>>n>>l>>m;

        for(i=0;i<n;i++)

        {

            cin>>x>>arr[i];

        }

        sort(arr,arr+n);

        cout<<"Case "<<k<<": "<<solve(0,m)<<endl;

    }

}