Submission #1000172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000172		Deepesson	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	40 ms	35668 KiB

kangaroo

#include <bits/stdc++.h>
#define MAX 2005
using ll = long long;
ll tab[MAX][MAX];
bool existe[MAX][MAX];
int N,A,B;
ll MOD = 1e9+7;
ll dp(ll C,ll K){
  //      std::cout<<C<<" "<<K<<"\n";
    if(K==N){
        return (C==1);
    }
    ll P = (K>A)+(K>B);

    if(existe[C][K])return tab[C][K];
    existe[C][K]=1;
    if(K==A||K==B){
    //    std::cout<<"yeah\n";
        int permite=0;
        if(K==N-1)permite=1;
        ll aumenta = dp(C,K+1)*(C-P+permite);
        ll cria = dp(C+1,K+1);
        return tab[C][K]=(aumenta+cria)%MOD;
    }else {
        if(K==N-1){
            if(C!=2)return 0;
            return tab[C][K]=dp(C-1,K+1);
        }
        ll une = 0;
        if(C){
            une=dp(C-1,K+1)*(C-P)*(C-1);
        }
        ll cria = dp(C+1,K+1);
        return tab[C][K]=(une+cria)%MOD;
    }
}
int main()
{
    std::cin>>N>>A>>B;--A;--B;
    std::cout<<dp(0,0)<<"\n";
}

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