oj.uz

Submission #173506

# Submission time Handle Problem Language Result Execution time Memory
173506 2020-01-04T10:18:09 Z Ruxandra985 Kangaroo (CEOI16_kangaroo) C++14
6 / 100
 2 ms 552 KB 
#include <cstdio>
#include <iostream>
#define MOD 1000000007
#define DIMN 2010
using namespace std;
long long dp[DIMN][DIMN] , fact[DIMN];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long n , cs , cf , i , j , nr;
    fscanf (fin,"%lld%lld%lld",&n,&cs,&cf);

    if (cs > cf)
        swap(cs,cf);

    dp[0][0] = 1;
    fact[0] = 1;
    for (i=1;i<=n;i++){
        fact[i] = (fact[i-1] * i)%MOD;
        if (i == cs || i == cf){ /// pe i il poti adauga doar intr o pozitie
            if (i == cs){
                for (j = 1 ; j <= i ; j ++)
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * j)%MOD;
            }
            else {
                dp[i][1] = dp[i-1][1];
                for (j = 2 ; j <= i ; j ++)
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (j - 1))%MOD;
                /// ai grija sa nu pui in lantul care incepe cu cs
            }
        }
        else {
            for (j = 1 ; j <= i ; j ++){

                if (i < cf && i > cs) /// exista UN lant care incepe cu cs, pe ala nu trb sa il cuplam
                    nr = (j + (j * (j-1))%MOD)%MOD;
                else if (i > cf){
                    /// exista UN lant care se termina cu cf
                    /// si unul care INCEPE cu cs
                    nr = (2 * (j-1) + ( (j - 1) * (j - 2))%MOD )%MOD;
                    if (i == n && j == 1) /// e momentul sa le unesti pe cs si cf
                        nr = 1;
                }
                else nr = ( j * (j+1) )%MOD;

                nr = (nr + MOD) % MOD;
                dp[i][j] = ( dp[i][j] + ( dp[i-1][j+1] * nr )%MOD  )%MOD;

                dp[i][j] = ( dp[i][j] + dp[i-1][j-1] )%MOD; /// pui i singur
            }
        }

    }
    fprintf (fout,"%lld",dp[n][1]);
    return 0;
}

Compilation message

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:12:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld%lld",&n,&cs,&cf);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Incorrect 2 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -