Submission #604791

#	Time	Username	Problem	Language	Result	Execution time	Memory
604791		faruk	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	700 ms	129264 KiB

kangaroo

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double

#define L 0
#define R 1

const ll mod = 1000000007;

using namespace std;

int memo[201][201][201][2], n, cs, cf;

int dp(int size, int curr, int end, int orient) {
    if (curr > size / 2 || curr == size / 2 && end > size / 2)
        curr = size - curr + 1, end = size - end + 1, orient = 1 - orient;

    if (memo[size][curr][end][orient] != -1)
        return memo[size][curr][end][orient];
    if (size == 1 && curr == 1 && end == 1)
        return 1;
    if (size != 1 && curr == end)
        return 0;
    
    int out = 0;
    if (orient == L) {
        for (int i = 1; i < curr; i++) {
            if (curr < end)
                out += dp(size - 1, i, end - 1, R), out %= mod;
            else
                out += dp(size - 1, i, end, R), out %= mod;
        }
    }
    else {
        for (int i = curr + 1; i <= size; i++) {
            if (curr < end)
                out += dp(size - 1, i - 1, end - 1, L), out %= mod;
            else
                out += dp(size - 1, i - 1, end, L), out %= mod;
        }
    }

    return memo[size][curr][end][orient] = out;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    memset(memo, -1, sizeof(memo));

    //freopen("kangaroo.in", "r", stdin);
    //freopen("kangaroo.out", "w", stdout);

    cin >> n >> cs >> cf;

    cout << (dp(n, cs, cf, L) + dp(n, cs, cf, R)) % mod << "\n";

    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int dp(int, int, int, int)':
kangaroo.cpp:16:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   16 |     if (curr > size / 2 || curr == size / 2 && end > size / 2)
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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