| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 612776 |
2022-07-30T00:54:33 Z |
stevancv |
Tents (JOI18_tents) |
C++14 |
|
599 ms |
40668 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e3 + 2;
const int mod = 1e9 + 7;
int Add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
return a;
}
int Mul(int a, int b) {
ll c = a; c *= b; c %= mod;
return c;
}
bool was[N][N];
int dp[N][N];
int Solve(int a, int b) {
if (a <= 0 || b <= 0) return 1;
if (a == 1 && b == 1) return 5;
if (was[a][b]) return dp[a][b];
was[a][b] = 1;
int ans = Solve(a - 1, b);
ll k = 4 * b;
ans = Add(ans, Mul(Solve(a - 1, b - 1), k));
k = b * (b - 1) / 2;
ans = Add(ans, Mul(Solve(a - 1, b - 2), k));
k = (a - 1) * b;
ans = Add(ans, Mul(Solve(a - 2, b - 1), k));
return dp[a][b] = ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w; cin >> h >> w;
cout << Add(Solve(h, w), -1) << en;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1756 KB |
Output is correct |
| 5 |
Correct |
2 ms |
712 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1756 KB |
Output is correct |
| 5 |
Correct |
2 ms |
712 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2584 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 15 |
Correct |
300 ms |
37192 KB |
Output is correct |
| 16 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 17 |
Correct |
26 ms |
7004 KB |
Output is correct |
| 18 |
Correct |
62 ms |
12620 KB |
Output is correct |
| 19 |
Correct |
275 ms |
39444 KB |
Output is correct |
| 20 |
Correct |
241 ms |
32568 KB |
Output is correct |
| 21 |
Correct |
151 ms |
20892 KB |
Output is correct |
| 22 |
Correct |
175 ms |
26308 KB |
Output is correct |
| 23 |
Correct |
125 ms |
28296 KB |
Output is correct |
| 24 |
Correct |
438 ms |
40668 KB |
Output is correct |
| 25 |
Correct |
339 ms |
34700 KB |
Output is correct |
| 26 |
Correct |
390 ms |
38092 KB |
Output is correct |
| 27 |
Correct |
599 ms |
39568 KB |
Output is correct |
