Submission #1117787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117787		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	520 ms	273480 KiB

kangaroo

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long

const int mod = 1e9 + 7;
int dp[205][205][205][2], n, s, f;

int dfs(int cur, int a, int b, int md){
    if(cur < 2) return 0;
    // cout << cur << " " << a << " " << b << " " << md << endl;
    if(dp[cur][a][b][md] != -1) return dp[cur][a][b][md];
    if(a == b or cur < a or cur < b)  return dp[cur][a][b][md] = 0;
    dp[cur][a][b][md] = 0;
    if(md){
        for(int i = a + 1; i <= cur; i++){
            if(i == b)  continue;
            // if(cur == 3)    cout << i << " " << endl;
            if(a > b)   dp[cur][a][b][md] += dfs(cur - 1, i - 1, b, !md);
            else    dp[cur][a][b][md] += dfs(cur - 1, i - 1, b - 1, !md);
        }
    }
    else{
        for(int i = a - 1; i >= 1; i--){
            if(i == b)  continue;
            // if(cur == 3)    cout << "i : " << cur << " " << i << " " << b << endl;
            if(a < b)   dp[cur][a][b][md] += dfs(cur - 1, i, b - 1, !md);
            else    dp[cur][a][b][md] += dfs(cur - 1, i, b, !md);
            // if(cur == 3)    cout << "i : " << cur << " " << i << " " << b << endl;

        }
    }
    dp[cur][a][b][md] %= mod;
    // cout << dp[cur][a][b][md] << endl << endl;
    return dp[cur][a][b][md];
}

void fmain(){
    cin >> n >> s >> f;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                dp[i][j][k][0] = dp[i][j][k][1] = -1;
            }
        }
    }
    dp[2][1][2][1] = 1, dp[2][2][1][0] = 1;
    cout << (dfs(n, s, f, 0) + dfs(n, s, f, 1)) % mod << endl;
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         for(int k = 1; k <= n; k++){
    //             cout << i << ", " << j << ", " << k << " : " << dp[i][j][k][0]  << " " <<  dp[i][j][k][1] << endl;
    //         }
    //     }
    // }
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
    // n = 6;
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         if(i == j){
    //             cout << 0 << " ";
    //             continue;
    //         }
    //         a = i, b = j;
    //         fmain();
    //     }
    //     cout << endl;
    // }
}

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