Submission #1293841

#TimeUsernameProblemLanguageResultExecution timeMemory
1293841xosqedemrufoKangaroo (CEOI16_kangaroo)C++20
51 / 100
732 ms589824 KiB
//Author RufatM
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ff first
#define ss second
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const int MOD=1000000007;
const int INF=1000000007;
const ll LINF=4e18;
const int MAXN=2005;
vector<vector<vector<int>>> dp;
signed main(){
    fastio;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.x","w",stdout);
    #endif
    int t=1;
    //cin >> t;
    while(t--){
        int n,s,l;
        cin >> n >> s >> l;
        dp.assign(n,vvi(n,vi(n+1,0)));
        s--,l--;
        dp[s][l][n]=1;
        s=n-s-1;
        l=n-l-1;
        dp[s][l][n]=1;
        for(int z=n;z>1;z--){
            for(int x=0;x<z;x++){
                for(int y=0;y<z;y++){
                    if(x==y){
                        continue;
                    }
                    if(dp[x][y][z]==0){
                        continue;
                    }
                    for(int i=0;i<z;i++){
                        if(i==x){
                            continue;
                        }
                        if((i<x and (z%2==0)) or (i>=x and (z%2==1))){
                            continue;
                        }
                        int left=i-(i>x);
                        int right=y-(y>x);
                        dp[left][right][z-1]+=dp[x][y][z];
                        if(dp[left][right][z-1]>=MOD){
                            dp[left][right][z-1]-=MOD;
                        }
                    }
                }
            }
        }
        cout<<dp[0][0][1]%MOD;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...