Submission #231774

#	Time	Username	Problem	Language	Result	Execution time	Memory
231774		nicolaalexandra	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	38 ms	14200 KiB

kangaroo

#include <bits/stdc++.h>
#define DIM 2010
#define MOD 1000000007
using namespace std;
int dp[DIM][DIM];
int n,i,j,k,t,st,fn;
int _(int x){
    while (x < 0)
        x += MOD;
    while (x >= MOD)
        x -= MOD;
    return x;
}
int main (){

    //ifstream cin ("kangaroo.in");
   // ofstream cout ("kangaroo.out");

    cin>>n>>st>>fn;
    /// dp[i][j]
    /// la un pas pot sa creez un grup nou sau sa unesc doua grupuri
    dp[0][0] = 1, k = 0;
    for (i=1;i<=n;i++){
        if (i == st || i == fn)
            k++;
        for (j=1;j<=i;j++){
            if (i == st || i == fn){
                dp[i][j] = _(dp[i-1][j-1] + dp[i-1][j]);
            } else {
                /// creez grup nou
                int cnt = j - k;
                dp[i][j] = _(dp[i][j] + 1LL*cnt*dp[i-1][j-1]%MOD);
                /// unesc doua grupuri
                dp[i][j] = _(dp[i][j] + 1LL*j*dp[i-1][j+1]%MOD);
            }}}

    cout<<dp[n][1];

    /*
    /// dp[i][j][k][0/1] - nr de permutari de lg i care incep pe j si se termina pe k si sa inceapa crescator / descrescator
    dp[2][1][2][0] = dp[2][2][1][1] = 1;

    for (i=3;i<=n;i++){
        for (j=1;j<=i;j++){
            for (k=j+1;k<=i;k++){

                if (j == 1){
                    for (t=2;t<=i;t++)
                        dp[i][j][k][0] = _(dp[i][j][k][0] + dp[i-1][t][k-1][1]);
                } else dp[i][j][k][0] = _(dp[i][j-1][k][0] - dp[i-1][j-1][k-1][1]);


                dp[i][j][k][1] = _(dp[i][j-1][k][1] + dp[i-1][j-1][k-1][0]);

                if (i%2)
                    dp[i][k][j][0] = dp[i][j][k][0], dp[i][k][j][1] = dp[i][j][k][1];
                else dp[i][k][j][0] = dp[i][j][k][1], dp[i][k][j][1] = dp[i][j][k][0];

            }
        }
    }

    if (st > fn)
        swap (st,fn);

    cout<<_(dp[n][st][fn][0] + dp[n][st][fn][1]);
    */

    return 0;
}

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