Submission #1216754

#TimeUsernameProblemLanguageResultExecution timeMemory
1216754horkaKangaroo (CEOI16_kangaroo)C++20
0 / 100
0 ms400 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int dp[41][41][41][2];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin>>n;
    int st,veg; cin>>st>>veg;
    for(int i=1; i<=n; i++)
    {
        if(i==st || i==veg) continue;
        dp[n-1][(i<st?i:i-1)][(st<veg?veg-1:veg)][(i<st?0:1)]=1;
    }
    if(n==2)
    {
        cout<<"1\n";
        return 0;
    }
    for(int i=n-1; i>1; i--)
    {
        for(int curr=1; curr<=i; curr++)
            for(int v=1; v<=i; v++)
                for(int last=0; last<2; last++)
                {
                    if(dp[i][curr][v][last]==0) continue;
                    if(last==1)
                    {
                        for(int kov=1; kov<curr; kov++)
                        dp[i-1][kov][(curr<v?v-1:v)][0]=(dp[i-1][kov][(curr<v?v-1:v)][0]+dp[i][curr][v][last])%MOD;
                    }
                    else
                    {
                        for(int kov=curr+1; kov<=i; kov++){
                        //if(i==2 && curr==1 && v==2 && last==0) cout<<"itt: "<<dp[i][curr][v][last]<<" "<<kov<<endl;
                            dp[i-1][kov-1][(curr<v?v-1:v)][1]=(dp[i-1][kov-1][(curr<v?v-1:v)][1]+dp[i][curr][v][last])%MOD;}
                    }
                }
    }
   // cout<<dp[2][1][2][0]<<endl;
    //5
    //cout<<dp[2][2][1][1]<<endl;
    //cout<<dp[2][1][2][0]<<endl;
    cout<<(dp[1][1][1][0]+dp[1][1][1][1])%MOD<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...