Submission #48308

#	Time	Username	Problem	Language	Result	Execution time	Memory
48308		wasyl	Kangaroo (CEOI16_kangaroo)	C++11	51 / 100	1293 ms	128176 KiB

kangaroo

#include <bits/stdc++.h>
#ifndef DBG
#define dbg(...)
#else
#define dbg(...) {cerr << "\033[1;96m"; __VA_ARGS__; cerr << "\033[0m";} 
#endif
#define bgn(...) begin(__VA_ARGS__)
#define rsz(...) resize(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define ddmp(...) dbg(dmp(__VA_ARGS__))
#define prt(...) print(cout, __VA_ARGS__)
#define dprt(...) dbg(print(cerr, __VA_ARGS__))
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define all(...) bgn(__VA_ARGS__), end(__VA_ARGS__)
#define siz(...) static_cast< int >((__VA_ARGS__).size())
using namespace std; using ll = long long;
template< typename... t > using V = vector< t... >;
template< typename... t > using outit = ostream_iterator< t... >;
template< typename t > void print(ostream& os, const t& a)
{os << a <<  '\n';} template< typename t, typename... v >
void print(ostream& os, const t& a, v&&... b){os << a << ' '; print(os, b...);}

constexpr int mod = 1e9 + 7, maxn = 2e2;

int n, cs, cf;
int dp[maxn + 1][maxn + 1][maxn + 1][2];

int kangaroo(int n, int cs, int cf, bool fl)
{
    if (dp[n][cs][cf][fl] != -1)
        return dp[n][cs][cf][fl];

    if (n > 1 and cs == cf)
        return dp[n][cs][cf][fl] = 0;

    if (n == 1 and cs == cf)
        return dp[n][cs][cf][fl] = 1;
    
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i == cs)
            continue;

        if ((not fl and i < cs) or (fl and i > cs))
            continue;

        int ncs = cs < i? i - 1 : i;
        int ncf = cs < cf? cf - 1 : cf;

        res = (res + kangaroo(n - 1, ncs, ncf, 1 - fl)) % mod;
    }

    return dp[n][cs][cf][fl] = res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> cs >> cf;

    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            for (int k = 0; k <= n; ++k)
                dp[i][j][k][0] = dp[i][j][k][1] = -1;

    prt((kangaroo(n, cs, cf, false) + kangaroo(n, cs, cf, true)) % mod);
}

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