oj.uz

Submission #231715

# Submission time Handle Problem Language Result Execution time Memory
231715 2020-05-14T14:17:55 Z nicolaalexandra Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 210
#define MOD 1000000007
using namespace std;
int dp[DIM][DIM][DIM][2];
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][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 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -