Submission #651441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651441	2022-10-18T18:30:07 Z	aebov	Tents (JOI18_tents)	C++17	100 / 100	256 ms	70804 KB

tents

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
#define pb push_back
using namespace std;

const ll mod = (ll)1e9 + 7;
ll mul(ll a, ll b){
	return 1LL * (a%mod) * (b%mod) % mod;
}
ll add(ll a, ll b){
	return ((a%mod) + (b%mod) ) % mod;
}
const int N = (int)3002;
ll dp[N][N];
int n, m;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for(int i = 0; i <= n; i ++){
		for(int j = 0; j <= m; j ++){
			if(i == 0 || j == 0){
				dp[i][j]=  1;
				continue;
			}
			dp[i][j] = dp[i][j-1];
			dp[i][j] = add(dp[i][j], mul(1LL * i * 4, dp[i-1][j-1]));
			if(j > 1)dp[i][j] = add(dp[i][j], mul(1LL * i * (j - 1)  , dp[i-1][j-2]));
			if(i > 1)dp[i][j] = add(dp[i][j], mul(1LL * i * (i - 1) / 2, dp[i-2][j-1]));
			//cout << i << " " << j <<  " : " << dp[i][j] - 1 << endl;
		}
	}
	cout << add( -1, dp[n][m]) << endl;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	456 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1740 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	4 ms	2132 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	456 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1740 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	4 ms	2132 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	4 ms	9684 KB	Output is correct
15	Correct	161 ms	55252 KB	Output is correct
16	Correct	11 ms	4052 KB	Output is correct
17	Correct	38 ms	12864 KB	Output is correct
18	Correct	45 ms	16976 KB	Output is correct
19	Correct	188 ms	62924 KB	Output is correct
20	Correct	151 ms	50832 KB	Output is correct
21	Correct	102 ms	33748 KB	Output is correct
22	Correct	98 ms	35364 KB	Output is correct
23	Correct	58 ms	26956 KB	Output is correct
24	Correct	256 ms	70804 KB	Output is correct
25	Correct	192 ms	61132 KB	Output is correct
26	Correct	221 ms	66504 KB	Output is correct
27	Correct	247 ms	69028 KB	Output is correct