Submission #798081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
798081	2023-07-30T10:59:02 Z	bonk	Tents (JOI18_tents)	C++14	100 / 100	256 ms	71156 KB

tents

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3002;
const ll mod = 1e9 + 7;

ll dp[N][N];

ll multi(ll a, ll b){
    return ((a % mod) * (b % mod)) % mod;
}

ll add(ll a, ll b){
    return (a + b) % mod;
}

ll f(ll x, ll y){
    if(x < 0 || y < 0) return 0;
    if(x == 0 || y == 0) return 1;

    auto &cur = dp[x][y];
    if(cur != -1) return cur;

    cur = add(
            add(
                add(
                    f(x - 1, y),
                    multi(4LL*y, f(x - 1, y - 1))
                ), 
                multi((y*(y - 1LL))/2LL, f(x - 1, y - 2))
            ), 
            multi(y*(x - 1LL), f(x - 2, y - 1))
        );

    return cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    int h, w; cin >> h >> w;

    cout << (f(h, w) - 1LL + mod) % mod << '\n';

    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	70740 KB	Output is correct
2	Correct	25 ms	70804 KB	Output is correct
3	Correct	23 ms	70760 KB	Output is correct
4	Correct	23 ms	70840 KB	Output is correct
5	Correct	24 ms	70744 KB	Output is correct
6	Correct	25 ms	70804 KB	Output is correct
7	Correct	24 ms	70860 KB	Output is correct
8	Correct	26 ms	70868 KB	Output is correct
9	Correct	29 ms	70820 KB	Output is correct
10	Correct	37 ms	70852 KB	Output is correct
11	Correct	30 ms	70728 KB	Output is correct
12	Correct	25 ms	70856 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	70740 KB	Output is correct
2	Correct	25 ms	70804 KB	Output is correct
3	Correct	23 ms	70760 KB	Output is correct
4	Correct	23 ms	70840 KB	Output is correct
5	Correct	24 ms	70744 KB	Output is correct
6	Correct	25 ms	70804 KB	Output is correct
7	Correct	24 ms	70860 KB	Output is correct
8	Correct	26 ms	70868 KB	Output is correct
9	Correct	29 ms	70820 KB	Output is correct
10	Correct	37 ms	70852 KB	Output is correct
11	Correct	30 ms	70728 KB	Output is correct
12	Correct	25 ms	70856 KB	Output is correct
13	Correct	28 ms	70824 KB	Output is correct
14	Correct	24 ms	70996 KB	Output is correct
15	Correct	176 ms	71032 KB	Output is correct
16	Correct	27 ms	70876 KB	Output is correct
17	Correct	53 ms	70828 KB	Output is correct
18	Correct	62 ms	70920 KB	Output is correct
19	Correct	214 ms	71044 KB	Output is correct
20	Correct	164 ms	70952 KB	Output is correct
21	Correct	100 ms	70960 KB	Output is correct
22	Correct	117 ms	71012 KB	Output is correct
23	Correct	120 ms	71156 KB	Output is correct
24	Correct	256 ms	71020 KB	Output is correct
25	Correct	190 ms	71044 KB	Output is correct
26	Correct	223 ms	71124 KB	Output is correct
27	Correct	230 ms	71048 KB	Output is correct