# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
796359 |
2023-07-28T10:18:52 Z |
anton |
Zapina (COCI20_zapina) |
C++17 |
|
134 ms |
3144 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 +7;
const int MAX_N = 350;
int n, nb_c[MAX_N][MAX_N+1], dp[MAX_N][MAX_N+1];
int C[MAX_N+1][MAX_N];
int expo(int a, int b){
if(b==0){
return 1;
}
if(b%2==1){
return (a*expo(a, b-1))%mod;
}
else{
return (expo(a, b/2)*expo(a, b/2))%mod;
}
}
signed main(){
cin>>n;
C[0][0] =1;
C[1][0] = 1;
C[1][1] = 1;
for(int i = 2; i<=n; i++){
for(int j =0; j<=n; j++){
C[i][j] = C[i-1][j];
if(j>0){
C[i][j] = (C[i][j]+ C[i-1][j-1])%mod;
}
}
cout<<endl;
}
for(int i = n-1; i>=0; i--){
for(int j = 0; j<=n; j++){
nb_c[i][j] = expo((n-i), j);
}
}
for(int i = n-1; i>=0; i--){
for(int j = 0; j<=n; j++){
int cost = i+1;
if(i==n-1){
if(j==cost){
dp[i][j] = 1;
}
else{
dp[i][j] = 0;
}
}
else{
for(int k = 0; k<=j; k++){
if(k!=cost){
dp[i][j] = (dp[i][j]+ (dp[i+1][j-k] * C[j][k])%mod)%mod;
}
}
if(j>=cost){
dp[i][j] = (dp[i][j]+ (nb_c[i+1][j-cost] * C[j][cost])%mod)%mod;
}
}
}
}
cout<<dp[0][n]<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
65 ms |
2516 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
15 ms |
1592 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
91 ms |
2700 KB |
Output is correct |
22 |
Correct |
12 ms |
1460 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
19 ms |
1684 KB |
Output is correct |
25 |
Correct |
13 ms |
1492 KB |
Output is correct |
26 |
Correct |
26 ms |
1868 KB |
Output is correct |
27 |
Correct |
124 ms |
3096 KB |
Output is correct |
28 |
Correct |
123 ms |
3032 KB |
Output is correct |
29 |
Correct |
124 ms |
3108 KB |
Output is correct |
30 |
Correct |
128 ms |
3012 KB |
Output is correct |
31 |
Correct |
127 ms |
3024 KB |
Output is correct |
32 |
Correct |
128 ms |
3036 KB |
Output is correct |
33 |
Correct |
129 ms |
3124 KB |
Output is correct |
34 |
Correct |
134 ms |
3092 KB |
Output is correct |
35 |
Correct |
132 ms |
3136 KB |
Output is correct |
36 |
Correct |
132 ms |
3104 KB |
Output is correct |
37 |
Correct |
133 ms |
3144 KB |
Output is correct |