Submission #558089

#	Time	Username	Problem	Language	Result	Execution time	Memory
558089		Alexandruabcde	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	340 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2005;
constexpr int MOD = 1e9 + 7;

int N, cs, cf;
int dp[NMAX][2][NMAX];

void Add (int &x, int y) {
    x = x + y;
    if (x >= MOD) x -= MOD;
}

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

    cin >> N >> cs >> cf;
    dp[0][0][cs-1] = 1;
    dp[0][1][cs-1] = 1;

    for (int i = 0; i < N-2; ++ i ) {
        for (int cnt_st = 0; cnt_st <= (N-2) - i; ++ cnt_st ) {
            int cnt_dr = (N-2) - i - cnt_st;

            assert(cnt_dr >= 0);

            for (int j = 1; j <= cnt_dr; ++ j )
                Add(dp[i+1][1][cnt_st + (j-1)], dp[i][0][cnt_st]);

            for (int j = 1; j <= cnt_st; ++ j )
                Add(dp[i+1][0][cnt_st-j], dp[i][1][cnt_st]);
        }
    }

    int sol = 0;
    Add(sol, dp[N-2][0][0]);
    Add(sol, dp[N-2][1][0]);

    cout << sol << '\n';

    return 0;
}

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