oj.uz

Submission #798424

# Submission time Handle Problem Language Result Execution time Memory
798424 2023-07-30T17:04:42 Z vjudge1 Tents (JOI18_tents) C++17
100 / 100
 123 ms 71496 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3030;
const ll mod = 1e9 + 7;

void add(ll &x, ll y) {
    x += y;
    x %= mod;
    if(x < 0) {
        x += mod;
    }
}

ll dp[N][N];

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for(int i = N; i --> 0; dp[i][0] = dp[0][i] = 1);
    for(int i = 1; i <= n; ++ i) {
          for(int j = 1; j <= m; ++ j) {
                add(dp[i][j], dp[i - 1][j]);
                add(dp[i][j], dp[i - 1][j - 1] * j * 4);
                if(j > 1) {
                    add(dp[i][j], dp[i - 1][j - 2] * (j * j - j) / 2);
                }
                if(i > 1) {
                    add(dp[i][j], dp[i - 2][j - 1] * j * (i - 1));   
                }
          }
    }
    add(dp[n][m], -1);
    cout << dp[n][m];
}

Compilation message

tents.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 6 ms 12500 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12748 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12620 KB Output is correct
9 Correct 4 ms 12492 KB Output is correct
10 Correct 5 ms 12872 KB Output is correct
11 Correct 5 ms 12500 KB Output is correct
12 Correct 6 ms 13260 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 6 ms 12500 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12748 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12620 KB Output is correct
9 Correct 4 ms 12492 KB Output is correct
10 Correct 5 ms 12872 KB Output is correct
11 Correct 5 ms 12500 KB Output is correct
12 Correct 6 ms 13260 KB Output is correct
13 Correct 6 ms 12524 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 87 ms 56224 KB Output is correct
16 Correct 9 ms 15288 KB Output is correct
17 Correct 22 ms 22228 KB Output is correct
18 Correct 25 ms 24656 KB Output is correct
19 Correct 90 ms 63352 KB Output is correct
20 Correct 72 ms 53152 KB Output is correct
21 Correct 51 ms 39296 KB Output is correct
22 Correct 51 ms 38860 KB Output is correct
23 Correct 34 ms 27180 KB Output is correct
24 Correct 116 ms 71496 KB Output is correct
25 Correct 96 ms 63408 KB Output is correct
26 Correct 123 ms 67960 KB Output is correct
27 Correct 112 ms 69956 KB Output is correct