Submission #535161

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535161	2022-03-09T14:26:35 Z	Lobo	Tents (JOI18_tents)	C++17	100 / 100	113 ms	71400 KB

tents

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 3030

int dp[maxn][maxn];
int mod = 1e9+7;

void solve() {
    int n, m;
    cin >> n >> m;

    int ans = 0;
    dp[n][m] = 1;
    for(int i = n; i >= 0; i--) {
        for(int j = m; j >= 0; j--) {
            dp[i][j]+= dp[i+1][j];

            dp[i][j]+= dp[i+1][j+1]*(j+1)*4;

            dp[i][j]+= dp[i+1][j+2]*(j+2)*(j+1)/2;

            dp[i][j]+= dp[i+2][j+1]*(j+1)*(i+1);

            dp[i][j]%= mod;

            // cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }

    for(int j = m; j >= 0; j--) ans+= dp[0][j];

    cout << (ans-1+mod)%mod << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	1356 KB	Output is correct
7	Correct	1 ms	704 KB	Output is correct
8	Correct	1 ms	1348 KB	Output is correct
9	Correct	1 ms	716 KB	Output is correct
10	Correct	2 ms	1736 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	2 ms	2124 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	1356 KB	Output is correct
7	Correct	1 ms	704 KB	Output is correct
8	Correct	1 ms	1348 KB	Output is correct
9	Correct	1 ms	716 KB	Output is correct
10	Correct	2 ms	1736 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	2 ms	2124 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	6 ms	9660 KB	Output is correct
15	Correct	73 ms	55132 KB	Output is correct
16	Correct	5 ms	4044 KB	Output is correct
17	Correct	15 ms	12748 KB	Output is correct
18	Correct	21 ms	16964 KB	Output is correct
19	Correct	86 ms	62896 KB	Output is correct
20	Correct	67 ms	50860 KB	Output is correct
21	Correct	45 ms	33708 KB	Output is correct
22	Correct	46 ms	35348 KB	Output is correct
23	Correct	35 ms	27052 KB	Output is correct
24	Correct	113 ms	71400 KB	Output is correct
25	Correct	84 ms	61720 KB	Output is correct
26	Correct	97 ms	67180 KB	Output is correct
27	Correct	101 ms	69472 KB	Output is correct