oj.uz

Submission #766295

# Submission time Handle Problem Language Result Execution time Memory
766295 2023-06-25T13:03:18 Z 1075508020060209tc Tents (JOI18_tents) C++14
48 / 100
 139 ms 165708 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
const int mod=1e9+7;
int n;int m;
int dp[310][310][310];
int cn2(int x){
return ((x*(x-1))/2)%mod;
}

signed main(){
cin>>n>>m;
dp[0][m][0]=1;

for(int H=0;H<=n-1;H++){
    for(int W=0;W<=m;W++){
        for(int h=0;h<=H;h++){
            if(dp[H][W][h]==0){continue;}
            dp[H+1][W][h]=(dp[H+1][W][h]+dp[H][W][h])%mod;
            if(W){
                dp[H+1][W-1][h]=(dp[H+1][W-1][h]+dp[H][W][h]*W*4)%mod;
                dp[H+1][W-1][h+1]=(dp[H+1][W-1][h+1]+dp[H][W][h]*W)%mod;
            }
            if(h){
                dp[H+1][W][h-1]=(dp[H+1][W][h-1]+dp[H][W][h]*h)%mod;
            }
            if(W>=2){
                dp[H+1][W-2][h]=(dp[H+1][W-2][h]+cn2(W)*dp[H][W][h])%mod;
            }
        }
    }
}
int ans=0;
for(int i=0;i<=m-1;i++){
   // cout<<i<<" "<<dp[n][i][0]<<"\n";
    ans+=dp[n][i][0];
    ans%=mod;
}
cout<<ans<<endl;

}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 9 ms 10420 KB Output is correct
6 Correct 28 ms 45108 KB Output is correct
7 Correct 16 ms 20128 KB Output is correct
8 Correct 21 ms 34772 KB Output is correct
9 Correct 1 ms 2132 KB Output is correct
10 Correct 61 ms 87292 KB Output is correct
11 Correct 2 ms 564 KB Output is correct
12 Correct 139 ms 165708 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 9 ms 10420 KB Output is correct
6 Correct 28 ms 45108 KB Output is correct
7 Correct 16 ms 20128 KB Output is correct
8 Correct 21 ms 34772 KB Output is correct
9 Correct 1 ms 2132 KB Output is correct
10 Correct 61 ms 87292 KB Output is correct
11 Correct 2 ms 564 KB Output is correct
12 Correct 139 ms 165708 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -