Submission #173517

#	Time	Username	Problem	Language	Result	Execution time	Memory
173517		Ruxandra985	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	50 ms	23004 KiB

kangaroo

#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;
                if (i <= cf || j != 2)
                    dp[i][j] = ( dp[i][j] + dp[i-1][j-1] )%MOD; /// pui i singur
                /// i > cf si j = 1 presupune ca ai un lant cu cs la inc si cf la final
                /// si nu mai ai cum sa adaugi i separat ca nu poti sa dai merge dupa
            }
        }

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

Compilation message (stderr)

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 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49