Submission #871691

#	Time	Username	Problem	Language	Result	Execution time	Memory
871691		Ghulam_Junaid	Kangaroo (CEOI16_kangaroo)	C++17	36 / 100	2036 ms	70432 KiB

kangaroo

/*

#include <bits/stdc++.h>
using namespace std;

ifstream fin("kangaroo.in");
ofstream fout("kangaroo.out");

// #define cin fin
// #define cout fout

typedef long long ll;

const ll mod = 1e9 + 7;
const ll N = 2005;
ll n, cs, cf, st, en;
map<pair<pair<ll, ll>, pair<ll, ll>>, ll> ans;

ll recur(ll n, ll cs, ll cf, ll dir){
    // cout << n << " " << cs << " " << cf << " " << dir << endl;

    if (cs == cf and n > 1)
        return 0;

    if (cs == cf)
        return 1;

    if (ans.find({{n, cs}, {cf, dir}}) != ans.end())
        return ans[{{n, cs}, {cf, dir}}];


    if (dir & 1){
        for (ll ns=1; ns<cs; ns++){
            bool sub = cs < cf;
            ans[{{n, cs}, {cf, dir}}] += recur(n - 1, ns, cf - sub, 2);
            ans[{{n, cs}, {cf, dir}}] %= mod;
        }
    }
    if (dir & 2){
        for (ll ns=cs; ns < n; ns++){
            bool sub = cs < cf;
            ans[{{n, cs}, {cf, dir}}] += recur(n - 1, ns, cf - sub, 1);
            ans[{{n, cs}, {cf, dir}}] %= mod;
        }
    }

    return ans[{{n, cs}, {cf, dir}}];
}

int main(){
    cin >> n >> cs >> cf;
    st = cs;
    en = cf;

    // for (int i=1; i<=n; i++)
    //     ans[{{1, i}, {i, 1}}] = ans[{{1, i}, {i, 2}}] = ans[{{1, i}, {i, 3}}] = 1;
    
    cout << recur(n, cs, cf, 3) << endl;
}

*/

#include <bits/stdc++.h>
using namespace std;

// ifstream fin("kangaroo.in");
// ofstream fout("kangaroo.out");

// #define cin fin
// #define cout fout

typedef long long ll;

const ll mod = 1e9 + 7;
const ll N = 205;

ll n, cs, cf, dp[N][N][N];
map<vector<ll>, bool> seen;

int main(){
    cin >> n >> cs >> cf;
    
    dp[1][1][1] = 1;
    queue<vector<ll>> q;
    q.push({1, 1, 1, 1});

    while (!q.empty()){
        auto v = q.front();
        q.pop();


        ll i = v[0];
        ll f = v[1];
        ll e = v[2];
        bool greater = v[3];

        if (i >= n)
            break;

        if (greater){
            for (ll ne = e + 1; ne <= (i + 1); ne ++){
                dp[i+1][f + (f >= ne)][ne] += dp[i][f][e];
                dp[i+1][f + (f >= ne)][ne] %= mod;
                
                vector<ll> vec = {i + 1, f + (f >= ne), ne, !greater};
                
                if (!seen[vec])
                    q.push(vec);
                seen[vec] = 1;
            }
        }
        else{
            for (ll ne = e; ne > 0; ne--){
                dp[i + 1][f + (f >= ne)][ne] += dp[i][f][e];
                dp[i + 1][f + (f >= ne)][ne] %= mod;

                vector<ll> vec = {i + 1, f + (f >= ne), ne, !greater};
                
                if (!seen[vec])
                    q.push(vec);
                seen[vec] = 1;
            }
        }
    }

    ll ans = dp[n][cs][cf];
    // cout << ans << endl;
    memset(dp, 0, sizeof dp);
    seen.clear();

    dp[1][1][1] = 1;
    while(q.size()) q.pop();
    q.push({1, 1, 1, 0});

    while (!q.empty()){
        auto v = q.front();
        q.pop();

        ll i = v[0];
        ll f = v[1];
        ll e = v[2];
        bool greater = v[3];

        // cout << i << " " << f << " " << e << " -- " << dp[4][2][3] << endl;

        if (i >= n)
            break;


        if (greater){
            for (ll ne = e + 1; ne <= (i + 1); ne ++){
                dp[i+1][f + (f >= ne)][ne] += dp[i][f][e];
                dp[i+1][f + (f >= ne)][ne] %= mod;
                
                vector<ll> vec = {i + 1, f + (f >= ne), ne, !greater};
                
                if (!seen[vec])
                    q.push(vec);
                seen[vec] = 1;
            }
        }
        else{
            for (ll ne = e; ne > 0; ne--){
                dp[i + 1][f + (f >= ne)][ne] += dp[i][f][e];
                dp[i + 1][f + (f >= ne)][ne] %= mod;
                // if (i == 3){
                //     cout << i << " " << f << " " << e << " -- " << i + 1 << " " << f + (f >= ne) << " " << ne << endl; 
                //     cout << dp[i][f][e] << " " << dp[i+1][f + (f >= ne)][ne]  << endl;
                //     cout << dp[4][2][3] << endl;
                // }
                vector<ll> vec = {i + 1, f + (f >= ne), ne, !greater};
                
                if (!seen[vec])
                    q.push(vec);
                seen[vec] = 1;
            }
        }
    }

    ans += dp[n][cs][cf];
    ans %= mod;

    cout << ans << endl;
}

/*

1 < 8 > 6 < _ > _ < _ > 2 < 3

5 : 2
6 : 2 + 2
7 : 2 + 2 + 1
8 : 2 + 2 + 1

total = 16.
*/

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