#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
const int MOD = 1e9 + 7;
ll dp[MAXN][MAXN];
int N,cs,cf;
ll solve(int atual,int comp){
if(comp < 0) return 0;
if(dp[atual][comp] != -1) return dp[atual][comp];
int lcomp = (atual > cs);
int rcomp = (atual > cf);
if(atual == N){
return dp[atual][comp] = (comp == 0);
}
ll total = 0;
if(atual == cs){
total += solve(atual+1,comp);// nova componente
total += solve(atual+1,comp-1)*comp;// conecta a alguma
}
else if(atual == cf){
total += solve(atual+1,comp);// nova componente
total += solve(atual+1,comp-1)*comp;// conecta a alguma
}
else{
total += solve(atual + 1,comp + 1); // nova componente
total += solve(atual+1,comp-1)*(comp)*(lcomp + (comp - 1) + rcomp); // conecta duas
}
return dp[atual][comp] = (total % MOD);
}
int main(){
memset(dp,-1,sizeof(dp));
cin >> N >> cs >> cf;
cout << solve(1,0) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31988 KB |
Output is correct |
2 |
Correct |
27 ms |
31988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31988 KB |
Output is correct |
2 |
Correct |
27 ms |
31988 KB |
Output is correct |
3 |
Correct |
27 ms |
32052 KB |
Output is correct |
4 |
Correct |
30 ms |
32108 KB |
Output is correct |
5 |
Correct |
28 ms |
32184 KB |
Output is correct |
6 |
Correct |
28 ms |
32220 KB |
Output is correct |
7 |
Correct |
31 ms |
32244 KB |
Output is correct |
8 |
Correct |
32 ms |
32252 KB |
Output is correct |
9 |
Correct |
27 ms |
32252 KB |
Output is correct |
10 |
Correct |
31 ms |
32252 KB |
Output is correct |
11 |
Correct |
30 ms |
32268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31988 KB |
Output is correct |
2 |
Correct |
27 ms |
31988 KB |
Output is correct |
3 |
Correct |
27 ms |
32052 KB |
Output is correct |
4 |
Correct |
30 ms |
32108 KB |
Output is correct |
5 |
Correct |
28 ms |
32184 KB |
Output is correct |
6 |
Correct |
28 ms |
32220 KB |
Output is correct |
7 |
Correct |
31 ms |
32244 KB |
Output is correct |
8 |
Correct |
32 ms |
32252 KB |
Output is correct |
9 |
Correct |
27 ms |
32252 KB |
Output is correct |
10 |
Correct |
31 ms |
32252 KB |
Output is correct |
11 |
Correct |
30 ms |
32268 KB |
Output is correct |
12 |
Correct |
35 ms |
32276 KB |
Output is correct |
13 |
Correct |
29 ms |
32276 KB |
Output is correct |
14 |
Correct |
27 ms |
32280 KB |
Output is correct |
15 |
Correct |
32 ms |
32288 KB |
Output is correct |
16 |
Correct |
32 ms |
32288 KB |
Output is correct |
17 |
Correct |
31 ms |
32288 KB |
Output is correct |
18 |
Correct |
28 ms |
32288 KB |
Output is correct |
19 |
Correct |
30 ms |
32300 KB |
Output is correct |
20 |
Correct |
33 ms |
32304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
31988 KB |
Output is correct |
2 |
Correct |
27 ms |
31988 KB |
Output is correct |
3 |
Correct |
27 ms |
32052 KB |
Output is correct |
4 |
Correct |
30 ms |
32108 KB |
Output is correct |
5 |
Correct |
28 ms |
32184 KB |
Output is correct |
6 |
Correct |
28 ms |
32220 KB |
Output is correct |
7 |
Correct |
31 ms |
32244 KB |
Output is correct |
8 |
Correct |
32 ms |
32252 KB |
Output is correct |
9 |
Correct |
27 ms |
32252 KB |
Output is correct |
10 |
Correct |
31 ms |
32252 KB |
Output is correct |
11 |
Correct |
30 ms |
32268 KB |
Output is correct |
12 |
Correct |
35 ms |
32276 KB |
Output is correct |
13 |
Correct |
29 ms |
32276 KB |
Output is correct |
14 |
Correct |
27 ms |
32280 KB |
Output is correct |
15 |
Correct |
32 ms |
32288 KB |
Output is correct |
16 |
Correct |
32 ms |
32288 KB |
Output is correct |
17 |
Correct |
31 ms |
32288 KB |
Output is correct |
18 |
Correct |
28 ms |
32288 KB |
Output is correct |
19 |
Correct |
30 ms |
32300 KB |
Output is correct |
20 |
Correct |
33 ms |
32304 KB |
Output is correct |
21 |
Correct |
44 ms |
32436 KB |
Output is correct |
22 |
Correct |
35 ms |
32436 KB |
Output is correct |
23 |
Correct |
35 ms |
32436 KB |
Output is correct |
24 |
Correct |
95 ms |
32452 KB |
Output is correct |
25 |
Correct |
109 ms |
32472 KB |
Output is correct |
26 |
Correct |
106 ms |
32584 KB |
Output is correct |
27 |
Correct |
99 ms |
32588 KB |
Output is correct |
28 |
Correct |
70 ms |
32588 KB |
Output is correct |