oj.uz

Submission #914337

# Submission time Handle Problem Language Result Execution time Memory
914337 2024-01-21T16:56:17 Z borisAngelov Tents (JOI18_tents) C++17
100 / 100
 191 ms 79348 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3005;
const int mod = 1e9 + 7;

int n, m;

bool bl[maxn][maxn];
long long dp[maxn][maxn];

long long f(int rows, int cols)
{
    if (rows < 0 || cols < 0)
    {
        return 0;
    }

    if (rows == 0 || cols == 0)
    {
        return 1;
    }

    if (bl[rows][cols] == true)
    {
        return dp[rows][cols];
    }

    bl[rows][cols] = true;

    long long ans = 0;

    ans += f(rows - 1, cols);
    ans %= mod;

    ans += (4LL * cols) * f(rows - 1, cols - 1);
    ans %= mod;

    ans += ((1LL * cols) * (1LL * cols - 1LL) / 2LL) * f(rows - 1, cols - 2);
    ans %= mod;

    ans += (1LL * cols) * (1LL * (rows - 1)) * f(rows - 2, cols - 1);
    ans %= mod;

    return dp[rows][cols] = ans;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    cout << f(n, m) - 1 << endl;

    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 3 ms 9564 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 3 ms 9564 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 12 ms 63032 KB Output is correct
15 Correct 121 ms 74576 KB Output is correct
16 Correct 3 ms 7512 KB Output is correct
17 Correct 14 ms 19036 KB Output is correct
18 Correct 32 ms 32728 KB Output is correct
19 Correct 151 ms 78932 KB Output is correct
20 Correct 108 ms 65372 KB Output is correct
21 Correct 65 ms 44372 KB Output is correct
22 Correct 77 ms 58196 KB Output is correct
23 Correct 53 ms 79184 KB Output is correct
24 Correct 191 ms 79348 KB Output is correct
25 Correct 148 ms 69972 KB Output is correct
26 Correct 161 ms 76768 KB Output is correct
27 Correct 166 ms 79004 KB Output is correct