Submission #506236

#	Time	Username	Problem	Language	Result	Execution time	Memory
506236		rodov	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	30 ms	24012 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) cout << k << endl;
                d[i][j] = (d[i-1][j+1]*j + d[i-1][j-1]*k) % MOD;
            }
        }
    cout << d[n][1] << endl;
    /*
    cin >> n;
    d[1][1] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++)
            d[i][j] = d[i-1][j]*(2*j) + d[i-1][j-1]*j  + d[i-1][j+1]*j;
    cout << d[n][1] << endl;
    */
    return 0;
}

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