제출 #1199860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199860		omarrrr	캥거루 (CEOI16_kangaroo)	C++20	6 / 100	2105 ms	367432 KiB

kangaroo

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define mpr make_pair

const ll N=2e6 + 10 , mod=1e9 + 7, inf=1e18;

using namespace std;

ll n,m,k,q,c,x,y;
ll t[N];
bool vis[2500];
ll dp[250][250][250][3];

ll solve(ll ind,ll f,ll d,ll l,ll r){
    if(l+r==0 ){
        if((d==1 && ind<f) || (d==0 && ind>f))
            return 1;
    }
//    if(dp[ind][l][r][d]!=-1)
//        return dp[ind][l][r][d];
    ll res=0;
    if(d==2){
        ll i=ind-1;
        ll a=l,b=r;
        while(i){
            if(!vis[i] && i!=f){
                a--;
                vis[i]=1;
                res+=solve(i,f,1,a,b);
                vis[i]=0;
                b++;
            }
            i--;
        }
        i=ind+1;
        a=l;b=r;
        while(i<=n){
            if(!vis[i] && i!=f){
                b--;
                vis[i]=1;
                res+=solve(i,f,0,a,b);
                vis[i]=0;
                a++;
            }
            i++;
        }
    }else if(d==0){
        ll i=ind-1;
        while(i){
            if(!vis[i] && i!=f){
                l--;
                vis[i]=1;
                res+=solve(i,f,1,l,r);
                vis[i]=0;
                r++;
            }
            i--;
        }
    }else{
        ll i=ind+1;
        while(i<=n){
            if(!vis[i] && i!=f){
                r--;
                vis[i]=1;
                res+=solve(i,f,0,l,r);
                vis[i]=0;
                l++;
            }
            i++;
        }
    }
    return dp[ind][l][r][d]=res;
}


int main(){
        ios_base::sync_with_stdio (0); cin.tie(0),cout.tie(0);

//    freopen("dining.in","r",stdin);
//    freopen("dining.out","w",stdout);




    ll T=1;
    //cin>>T;
    while(T--){
        ll a,b;
        cin>>n>>a>>b;
        //cout<<a<<" "<<b<<"\n";
        memset(dp,-1,sizeof(dp));
        vis[a]=1;
        cout<<solve(a,b,2,a-1-(b<a),n-a-(b>a))%mod<<"\n";












    }


    return 0;
}

/*


3 1
1 3 10
1 2 4
2 3 4


*/

• Subtask 1: 6 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49