Submission #77890

#	Time	Username	Problem	Language	Result	Execution time	Memory
77890		triplem5ds	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	1086 ms	135728 KiB

kangaroo

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int,int>;
using ll = long long;

const int N = 2e5+5;
const int mod = 1e9 + 7;

/*
    IDEA:
    Solution for first subtask is a mask where dp[idx][mask][lastDir]
    Solution for second and third subtask is dp[CForder][L][R][lastDir] as long as i don't go to
    the CF cell i am safe
*/

int dp[205][205][205][2];

int solve(int ord, int l, int r, bool f){
    if(l+r == 1)
        return (l && (!f)) || (r && f);
    int &ret = dp[ord][l][r][f];
    if(~ret)
        return ret;
    ret = 0;
    if(!f){
        for(int i = 0; i < l; i++){
            /// i'll jump to the i-th cell
            if(ord == i)continue;
            if(i < ord){
                ret += solve(ord-1,i,r+(l-i-1),f ^ 1);
            }   else{
                ret += solve(ord,i,r+(l-i-1),f ^ 1);
            }
            if(ret >= mod)
                ret -= mod;
            }
    }  else{
        for(int i = 0; i < r; i++){
            if(l + i == ord)continue;
            if(l + i < ord){
                ret += solve(ord-1,l+i,r-i-1,f^1);
            }   else {
                ret += solve(ord,l+i,r-i-1,f^1);
            }
            if(ret >= mod)ret -= mod;
        }
    }
    return ret;
}


int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    memset(dp,-1,sizeof dp);
    int n, cs, cf;
    cin >> n >> cs >> cf;
    cs--,cf--;
    cout << (solve(cf-(cs<cf),cs,n-cs-1,1) + solve(cf-(cs<cf),cs,n-cs-1,0))%mod << '\n';

    return 0;
}

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