Submission #506237

#	Time	Username	Problem	Language	Result	Execution time	Memory
506237		rodov	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	16 ms	24036 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
long long n,s,f,k;
long long d[5007][5007];
const long long MOD = 1000000007;
int main() {
    cin >> n >> s >> f;
    d[1][1] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++) {
            if(i==s || i==f) d[i][j] = (d[i-1][j-1]+d[i-1][j])%MOD;
            else {
                k = j;
                if(i>s) k--;
                if(i>f) k--;
                if(k<0) k = 0;
                d[i][j] = (d[i-1][j+1]*j + d[i-1][j-1]*k) % MOD;
            }
        }
    cout << d[n][1] << endl;

    return 0;
}

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