Submission #119956

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
119956	2019-06-22T17:48:57 Z	arman_ferdous	Tents (JOI18_tents)	C++14	100 / 100	364 ms	71472 KB

tents

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 3010;
const int MOD = 1e9+7;

ll n, m;
ll dp[N][N];

void add(ll &x, ll y) { x += y; if(x >= MOD) x -= MOD; }

ll DP(ll r, ll c) {
	if(r <= 0 || c <= 0) return 1;
	if(dp[r][c] != -1) return dp[r][c];
	dp[r][c] = DP(r - 1, c);
	add(dp[r][c], (4ll * c * DP(r - 1, c - 1) % MOD) );
	add(dp[r][c], (((c * (c - 1)) >> 1) * DP(r - 1, c - 2) % MOD) );
	add(dp[r][c], (c * (r - 1) * DP(r - 2, c - 1) % MOD) );

	return dp[r][c];
}

int main() {
	scanf("%lld %lld", &n, &m);
	memset(dp, -1, sizeof dp);
	printf("%lld\n", (DP(n, m) - 1 + MOD) % MOD);
	return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	71288 KB	Output is correct
2	Correct	57 ms	71260 KB	Output is correct
3	Correct	57 ms	71160 KB	Output is correct
4	Correct	58 ms	71188 KB	Output is correct
5	Correct	58 ms	71272 KB	Output is correct
6	Correct	57 ms	71212 KB	Output is correct
7	Correct	56 ms	71264 KB	Output is correct
8	Correct	57 ms	71200 KB	Output is correct
9	Correct	57 ms	71212 KB	Output is correct
10	Correct	58 ms	71260 KB	Output is correct
11	Correct	58 ms	71308 KB	Output is correct
12	Correct	57 ms	71308 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	71288 KB	Output is correct
2	Correct	57 ms	71260 KB	Output is correct
3	Correct	57 ms	71160 KB	Output is correct
4	Correct	58 ms	71188 KB	Output is correct
5	Correct	58 ms	71272 KB	Output is correct
6	Correct	57 ms	71212 KB	Output is correct
7	Correct	56 ms	71264 KB	Output is correct
8	Correct	57 ms	71200 KB	Output is correct
9	Correct	57 ms	71212 KB	Output is correct
10	Correct	58 ms	71260 KB	Output is correct
11	Correct	58 ms	71308 KB	Output is correct
12	Correct	57 ms	71308 KB	Output is correct
13	Correct	56 ms	71216 KB	Output is correct
14	Correct	58 ms	71332 KB	Output is correct
15	Correct	232 ms	71388 KB	Output is correct
16	Correct	56 ms	71252 KB	Output is correct
17	Correct	70 ms	71288 KB	Output is correct
18	Correct	100 ms	71348 KB	Output is correct
19	Correct	279 ms	71460 KB	Output is correct
20	Correct	221 ms	71432 KB	Output is correct
21	Correct	143 ms	71416 KB	Output is correct
22	Correct	159 ms	71412 KB	Output is correct
23	Correct	127 ms	71460 KB	Output is correct
24	Correct	364 ms	71472 KB	Output is correct
25	Correct	270 ms	71448 KB	Output is correct
26	Correct	307 ms	71448 KB	Output is correct
27	Correct	345 ms	71468 KB	Output is correct