Submission #1277082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277082		herominhsteve	Kangaroo (CEOI16_kangaroo)	C++20	0 / 100	0 ms	332 KiB

kangaroo

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "kangaroo"
#define allof(x) x.begin(),x.end()
using namespace std;

const long long MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, cs, cf;
    cin >> n >> cs >> cf;

    vector<vector<long long>> dpUp(n+1, vector<long long>(n+1, 0));
    vector<vector<long long>> dpDown(n+1, vector<long long>(n+1, 0));
    
    dpUp[1][cs] = dpDown[1][cs] = 1;

    for (int len = 2; len <= n; len++) {
        vector<long long> prefUp(n+2, 0), prefDown(n+2, 0);

        for (int j = 1; j <= n; j++) {
            prefUp[j] = (prefUp[j-1] + dpUp[len-1][j]) % MOD;
            prefDown[j] = (prefDown[j-1] + dpDown[len-1][j]) % MOD;
        }

        for (int j = 1; j <= n; j++) {
            dpDown[len][j] = prefUp[j-1];  
            dpUp[len][j] = (prefDown[n] - prefDown[j] + MOD) % MOD;
        }
    }

    cout << (dpUp[n][cf] + dpDown[n][cf]) % MOD << el;
}

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