Submission #1016512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1016512	2024-07-08T07:22:18 Z	fryingduc	Tents (JOI18_tents)	C++17	100 / 100	88 ms	35668 KB

tents

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

const int maxn = 3005;
const int mod = 1e9 + 7;
int w, h;
int f[maxn][maxn];

int add(int x, int y) {
    if(y < 0) y += mod;
    x = x + y;
    if(x >= mod) x -= mod;
    return x;
}
int c2(int x) {
    return 1ll * x * (x - 1) / 2 % mod;
}
void solve() {
    cin >> h >> w;
    for(int i = 0; i <= h; ++i) f[i][0] = 1;
    for(int i = 0; i <= w; ++i) f[0][i] = 1;
    for(int i = 1; i <= h; ++i) {
        for(int j = 1; j <= w; ++j) {
            // add one tent
            f[i][j] = 1ll * f[i - 1][j - 1] * j % mod * 4 % mod; 
            
            // add two tents in same row 
            f[i][j] = add(f[i][j], 1ll * f[i - 2][j - 1] * (i - 1) % mod * j % mod);
            
            // add two tents in same col 
            f[i][j] = add(f[i][j], 1ll * f[i - 1][j - 2] * c2(j) % mod);
            
            // do nothing
            f[i][j] = add(f[i][j], f[i - 1][j]);
        }
    }
    
    cout << add(f[h][w], -1);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	2 ms	4560 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	2 ms	4560 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	3 ms	29020 KB	Output is correct
15	Correct	56 ms	33452 KB	Output is correct
16	Correct	5 ms	4700 KB	Output is correct
17	Correct	13 ms	8660 KB	Output is correct
18	Correct	17 ms	14940 KB	Output is correct
19	Correct	71 ms	35668 KB	Output is correct
20	Correct	56 ms	29272 KB	Output is correct
21	Correct	35 ms	21080 KB	Output is correct
22	Correct	34 ms	27224 KB	Output is correct
23	Correct	22 ms	35420 KB	Output is correct
24	Correct	88 ms	35668 KB	Output is correct
25	Correct	73 ms	31400 KB	Output is correct
26	Correct	76 ms	35508 KB	Output is correct
27	Correct	86 ms	35416 KB	Output is correct