oj.uz

Submission #236926

# Submission time Handle Problem Language Result Execution time Memory
236926 2020-06-03T21:01:53 Z aryan12 Tents (JOI18_tents) C++17
100 / 100
 475 ms 71416 KB 
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long N = 3010;
long long dp[N][N];

long long Recur(long long row, long long col) {
    if(row < 0 || col < 0)
        return 0;
    if(row == 0 || col == 0)
        return 1;
    if(dp[row][col] != -1)
        return dp[row][col];
    long long ans = 0, temp = 0;

    //the row is empty
    temp = Recur(row, col - 1);
    ans = temp;

    //1 tent facing anywhere
    temp = ((Recur(row - 1, col - 1) * row) % MOD * 4) % MOD;
    ans = (ans + temp) % MOD;

    //2 tents facing each other (row-wise)
    temp = (Recur(row - 2, col - 1) * (((row * (row - 1)) / 2) % MOD)) % MOD;
    ans = (ans + temp) % MOD;

    //2 tents facing each other (column-wise)
    temp = (Recur(row - 1, col - 2));
    long long x = row * (col - 1) % MOD;
    temp *= x;
    temp %= MOD;
    ans = (ans + temp) % MOD;
    dp[row][col] = ans;
    return ans;
}

void Solve() {
    long long n, m;
    cin >> n >> m;
    for(long long i = 0; i <= n; i++) {
        for(long long j = 0; j <= m; j++) {
            dp[i][j] = -1;
        }
    }
    long long ans = Recur(n, m) - 1;
    if(ans < 0)
        ans += MOD;
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Solve();
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 1408 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 9 ms 2304 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 1408 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 9 ms 2304 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 9 ms 9728 KB Output is correct
15 Correct 234 ms 55428 KB Output is correct
16 Correct 18 ms 4224 KB Output is correct
17 Correct 53 ms 13056 KB Output is correct
18 Correct 58 ms 17152 KB Output is correct
19 Correct 291 ms 63232 KB Output is correct
20 Correct 231 ms 51148 KB Output is correct
21 Correct 148 ms 34048 KB Output is correct
22 Correct 132 ms 35584 KB Output is correct
23 Correct 32 ms 27136 KB Output is correct
24 Correct 410 ms 71416 KB Output is correct
25 Correct 323 ms 61568 KB Output is correct
26 Correct 335 ms 67192 KB Output is correct
27 Correct 475 ms 69368 KB Output is correct