Submission #708030

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708030	2023-03-10T19:50:23 Z	Spade1	Tents (JOI18_tents)	C++14	100 / 100	184 ms	70908 KB

tents

#include<bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 3e3 + 10;
const int M = 1e9 + 7;
ll dp[N][N];

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

void solve() {
    int h, w; cin >> h >> w;
    for (int i = 0; i <= h; ++i) dp[i][0] = 1;
    for (int j = 0; j <= w; ++j) dp[0][j] = 1;
    for (ll i = 1; i <= h; ++i) {
        for (ll j = 1; j <= w; ++j) {
            dp[i][j] = add(dp[i][j], dp[i-1][j]);
            dp[i][j] = add(dp[i][j], 4*j*dp[i-1][j-1]);
            if (i > 1) dp[i][j] = add(dp[i][j], (i-1)*j*dp[i-2][j-1]);
            if (j > 1) dp[i][j] = add(dp[i][j], j*(j-1)/2*dp[i-1][j-2]);
        }
    }
    cout << dp[h][w]-1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1748 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	3 ms	2132 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1748 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	3 ms	2132 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	4 ms	9684 KB	Output is correct
15	Correct	115 ms	55176 KB	Output is correct
16	Correct	9 ms	4044 KB	Output is correct
17	Correct	27 ms	12748 KB	Output is correct
18	Correct	34 ms	17008 KB	Output is correct
19	Correct	136 ms	62968 KB	Output is correct
20	Correct	109 ms	50908 KB	Output is correct
21	Correct	71 ms	33692 KB	Output is correct
22	Correct	73 ms	35384 KB	Output is correct
23	Correct	43 ms	27056 KB	Output is correct
24	Correct	184 ms	70908 KB	Output is correct
25	Correct	144 ms	61252 KB	Output is correct
26	Correct	153 ms	66744 KB	Output is correct
27	Correct	169 ms	69056 KB	Output is correct