Submission #93762

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93762	2019-01-11T02:57:01 Z	silxikys	Tents (JOI18_tents)	C++14	100 / 100	549 ms	71308 KB

tents

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

const int maxn = 3005, M = 1e9+7;
ll dp[maxn][maxn];
int madd(int a, int b) {
    a += b;
    while (a > M) a -= M;
    return a;
}

int mult(int a, int b) {
    return (1LL*a*b) % M;
}

ll ch2(int a) {
    return ((1LL*a*(a-1))/2) % M;
}

ll f(int i, int j) {
    if (i < 0 || j < 0) return 0;
    if (i == 0 || j == 0) return 1;
    ll& res = dp[i][j];
    if (res != -1) return res;
    res = 0;
    res = madd(res,mult(ch2(j),f(i-1,j-2)));
    res = madd(res,mult(mult(4,j),f(i-1,j-1)));
    res = madd(res,mult(mult(j,i-1),f(i-2,j-1)));
    res = madd(res,f(i-1,j));
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int H, W; cin >> H >> W;
    memset(dp,-1,sizeof dp);
    cout << (f(H,W)+M-1) % M << '\n';

    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	71032 KB	Output is correct
2	Correct	58 ms	71160 KB	Output is correct
3	Correct	57 ms	71032 KB	Output is correct
4	Correct	57 ms	71088 KB	Output is correct
5	Correct	57 ms	71160 KB	Output is correct
6	Correct	58 ms	71024 KB	Output is correct
7	Correct	57 ms	71032 KB	Output is correct
8	Correct	57 ms	71032 KB	Output is correct
9	Correct	56 ms	71032 KB	Output is correct
10	Correct	54 ms	70996 KB	Output is correct
11	Correct	56 ms	71004 KB	Output is correct
12	Correct	61 ms	71032 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	71032 KB	Output is correct
2	Correct	58 ms	71160 KB	Output is correct
3	Correct	57 ms	71032 KB	Output is correct
4	Correct	57 ms	71088 KB	Output is correct
5	Correct	57 ms	71160 KB	Output is correct
6	Correct	58 ms	71024 KB	Output is correct
7	Correct	57 ms	71032 KB	Output is correct
8	Correct	57 ms	71032 KB	Output is correct
9	Correct	56 ms	71032 KB	Output is correct
10	Correct	54 ms	70996 KB	Output is correct
11	Correct	56 ms	71004 KB	Output is correct
12	Correct	61 ms	71032 KB	Output is correct
13	Correct	59 ms	71004 KB	Output is correct
14	Correct	60 ms	71160 KB	Output is correct
15	Correct	392 ms	71308 KB	Output is correct
16	Correct	60 ms	71056 KB	Output is correct
17	Correct	81 ms	71032 KB	Output is correct
18	Correct	127 ms	71032 KB	Output is correct
19	Correct	453 ms	71304 KB	Output is correct
20	Correct	301 ms	71160 KB	Output is correct
21	Correct	188 ms	71132 KB	Output is correct
22	Correct	224 ms	71260 KB	Output is correct
23	Correct	174 ms	71288 KB	Output is correct
24	Correct	543 ms	71288 KB	Output is correct
25	Correct	380 ms	71288 KB	Output is correct
26	Correct	436 ms	71288 KB	Output is correct
27	Correct	549 ms	71288 KB	Output is correct