oj.uz

Submission #231773

# Submission time Handle Problem Language Result Execution time Memory
231773 2020-05-14T17:25:14 Z nicolaalexandra Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 5 ms 384 KB 
#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++){

        for (j=1;j<=i;j++){
            if (i == st || i == fn){
                k++;
                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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct