# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
173517 | 2020-01-04T11:27:31 Z | Ruxandra985 | Kangaroo (CEOI16_kangaroo) | C++14 | 50 ms | 23004 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; 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 504 KB | Output is correct |
4 | Correct | 2 ms | 476 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 508 KB | Output is correct |
8 | Correct | 2 ms | 632 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 504 KB | Output is correct |
4 | Correct | 2 ms | 476 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 508 KB | Output is correct |
8 | Correct | 2 ms | 632 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 3 ms | 1272 KB | Output is correct |
13 | Correct | 3 ms | 1276 KB | Output is correct |
14 | Correct | 3 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 1276 KB | Output is correct |
16 | Correct | 3 ms | 1272 KB | Output is correct |
17 | Correct | 3 ms | 1272 KB | Output is correct |
18 | Correct | 3 ms | 1148 KB | Output is correct |
19 | Correct | 3 ms | 1272 KB | Output is correct |
20 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 504 KB | Output is correct |
4 | Correct | 2 ms | 476 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 508 KB | Output is correct |
8 | Correct | 2 ms | 632 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 3 ms | 1272 KB | Output is correct |
13 | Correct | 3 ms | 1276 KB | Output is correct |
14 | Correct | 3 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 1276 KB | Output is correct |
16 | Correct | 3 ms | 1272 KB | Output is correct |
17 | Correct | 3 ms | 1272 KB | Output is correct |
18 | Correct | 3 ms | 1148 KB | Output is correct |
19 | Correct | 3 ms | 1272 KB | Output is correct |
20 | Correct | 3 ms | 1272 KB | Output is correct |
21 | Correct | 9 ms | 4600 KB | Output is correct |
22 | Correct | 10 ms | 5112 KB | Output is correct |
23 | Correct | 11 ms | 5624 KB | Output is correct |
24 | Correct | 50 ms | 23004 KB | Output is correct |
25 | Correct | 50 ms | 23004 KB | Output is correct |
26 | Correct | 50 ms | 23004 KB | Output is correct |
27 | Correct | 50 ms | 22904 KB | Output is correct |
28 | Correct | 32 ms | 15224 KB | Output is correct |