Submission #198344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198344	2020-01-25T16:31:44 Z	Malomalomalomalo	Tents (JOI18_tents)	C++14	100 / 100	743 ms	41064 KB

tents

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int MOD = 1e9+7;

int mul(int x,int y){
	return (1LL * x * y) % MOD;
}

int add(int x,int y){
	int res = x + y;
	while(res >= MOD)res-=MOD;
	return res;
}

const int N = 3e3 + 5;
int dp[N][N];
bool vis[N][N];
int inv = (MOD+1)/2;

int gdp(int n, int m){
	if(n < 0 || m < 0)return 0;
	if(n == 0 || m == 0)return 1;
	if(!vis[n][m]){
		vis[n][m] = 1;	
		gadd(dp[n][m], mul(mul(m,add(m,MOD-1)),mul(gdp(n-1,m-2),inv)));
		gadd(dp[n][m], mul(mul(4,m),gdp(n-1,m-1)));
		gadd(dp[n][m], mul(mul(m, add(n,MOD-1)), gdp(n-2,m-1)));
		gadd(dp[n][m], gdp(n-1,m));
	}
	return dp[n][m];
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	cout << add(gdp(n,m),MOD-1) << '\n';
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	632 KB	Output is correct
4	Correct	4 ms	1784 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	6 ms	2040 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	5 ms	2168 KB	Output is correct
9	Correct	3 ms	1144 KB	Output is correct
10	Correct	7 ms	2552 KB	Output is correct
11	Correct	0 ms	376 KB	Output is correct
12	Correct	11 ms	2680 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	632 KB	Output is correct
4	Correct	4 ms	1784 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	6 ms	2040 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	5 ms	2168 KB	Output is correct
9	Correct	3 ms	1144 KB	Output is correct
10	Correct	7 ms	2552 KB	Output is correct
11	Correct	0 ms	376 KB	Output is correct
12	Correct	11 ms	2680 KB	Output is correct
13	Correct	3 ms	248 KB	Output is correct
14	Correct	24 ms	16632 KB	Output is correct
15	Correct	511 ms	37508 KB	Output is correct
16	Correct	7 ms	2168 KB	Output is correct
17	Correct	41 ms	7160 KB	Output is correct
18	Correct	104 ms	12700 KB	Output is correct
19	Correct	567 ms	39800 KB	Output is correct
20	Correct	444 ms	32764 KB	Output is correct
21	Correct	228 ms	20984 KB	Output is correct
22	Correct	306 ms	26420 KB	Output is correct
23	Correct	218 ms	28380 KB	Output is correct
24	Correct	743 ms	41064 KB	Output is correct
25	Correct	540 ms	34860 KB	Output is correct
26	Correct	628 ms	38392 KB	Output is correct
27	Correct	700 ms	39672 KB	Output is correct