Submission #1113164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113164	2024-11-16T01:34:38 Z	onlk97	Tents (JOI18_tents)	C++14	100 / 100	131 ms	70888 KB

tents

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
const int mod=1e9+7LL;
int dp[3010][3010];
void solve(){
    int n,m;
    cin>>n>>m;
    dp[0][0]=1;
    for (int i=0; i<n; i++){
        for (int j=0; j<=m; j++){
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j]%=mod;
            if (j<m){
                dp[i+1][j+1]+=4*dp[i][j]*(m-j);
                dp[i+1][j+1]%=mod;
            }
            if (j<m-1){
                dp[i+1][j+2]+=dp[i][j]*((m-j)*(m-j-1)/2%mod);
                dp[i+1][j+2]%=mod;
            }
            if (i<n-1&&j<m){
                dp[i+2][j+1]+=dp[i][j]*((m-j)*(n-i-1)%mod);
                dp[i+2][j+1]%=mod;
            }
        }
    }
    int ans=0;
    for (int i=0; i<=m; i++) ans=(ans+dp[n][i])%mod;
    cout<<(ans+mod-1)%mod<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	636 KB	Output is correct
4	Correct	1 ms	1104 KB	Output is correct
5	Correct	2 ms	848 KB	Output is correct
6	Correct	2 ms	1360 KB	Output is correct
7	Correct	1 ms	848 KB	Output is correct
8	Correct	2 ms	1360 KB	Output is correct
9	Correct	1 ms	1020 KB	Output is correct
10	Correct	2 ms	1872 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	3 ms	2128 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	636 KB	Output is correct
4	Correct	1 ms	1104 KB	Output is correct
5	Correct	2 ms	848 KB	Output is correct
6	Correct	2 ms	1360 KB	Output is correct
7	Correct	1 ms	848 KB	Output is correct
8	Correct	2 ms	1360 KB	Output is correct
9	Correct	1 ms	1020 KB	Output is correct
10	Correct	2 ms	1872 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	3 ms	2128 KB	Output is correct
13	Correct	1 ms	504 KB	Output is correct
14	Correct	8 ms	9808 KB	Output is correct
15	Correct	100 ms	55112 KB	Output is correct
16	Correct	6 ms	4176 KB	Output is correct
17	Correct	21 ms	13000 KB	Output is correct
18	Correct	26 ms	17404 KB	Output is correct
19	Correct	102 ms	63048 KB	Output is correct
20	Correct	83 ms	51016 KB	Output is correct
21	Correct	57 ms	33796 KB	Output is correct
22	Correct	56 ms	35400 KB	Output is correct
23	Correct	37 ms	27208 KB	Output is correct
24	Correct	131 ms	70888 KB	Output is correct
25	Correct	102 ms	61448 KB	Output is correct
26	Correct	114 ms	66896 KB	Output is correct
27	Correct	129 ms	69096 KB	Output is correct