oj.uz

Submission #1101113

# Submission time Handle Problem Language Result Execution time Memory
1101113 2024-10-15T14:50:21 Z TgX_2 Tents (JOI18_tents) C++17
100 / 100
 178 ms 71536 KB 
/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

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

#define FOR(i, a, b)       for (int i = (a), _b = (b); i <= _b; i += 1)
#define FORD(i, a, b)      for (int i = (a), _b = (b); i >= _b; i -= 1)

#define fi                 first
#define se                 second
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"
#define ___                << " "

#define ______________TgX______________ main()
#define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

struct custom {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<class T1, class T2> using cmap = unordered_map<T1, T2, custom>;

template<typename T1, typename T2>
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2>
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

const int maxn = 3007;
const int mod  = 1e9 + 7;
int n, m;

int f[maxn][maxn];
int dp(int i, int j) {
    if (i < 0 or j < 0) return 0;
    if (i == 0 or j == 0) return 1;

    int &ans = f[i][j];
    if (ans != -1) return ans;

    ans = 0;
    (ans += dp(i, j - 1)) %= mod;
    (ans += ((4 * i) % mod * dp(i - 1, j - 1)) % mod) %= mod;
    (ans += (i * (i - 1) / 2 % mod * dp(i - 2, j - 1)) % mod) %= mod;
    (ans += ((i * (j - 1)) % mod * dp(i - 1, j - 2)) % mod) %= mod;
    return ans;
}

void process() {
    cin >> n >> m;
    memo(f, -1);

    cout << (dp(n, m) - 1 + mod) % mod;

}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }
    process();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." __ ;
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message

tents.cpp:21:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | #define ______________TgX______________ main()
      |                                         ^~~~
tents.cpp:84:1: note: in expansion of macro '______________TgX______________'
   84 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp: In function 'int main()':
tents.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("temp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("temp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 70992 KB Output is correct
2 Correct 9 ms 71068 KB Output is correct
3 Correct 9 ms 71148 KB Output is correct
4 Correct 9 ms 70992 KB Output is correct
5 Correct 10 ms 71248 KB Output is correct
6 Correct 9 ms 70992 KB Output is correct
7 Correct 10 ms 71248 KB Output is correct
8 Correct 9 ms 70992 KB Output is correct
9 Correct 9 ms 70992 KB Output is correct
10 Correct 10 ms 71260 KB Output is correct
11 Correct 9 ms 71248 KB Output is correct
12 Correct 11 ms 71248 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 70992 KB Output is correct
2 Correct 9 ms 71068 KB Output is correct
3 Correct 9 ms 71148 KB Output is correct
4 Correct 9 ms 70992 KB Output is correct
5 Correct 10 ms 71248 KB Output is correct
6 Correct 9 ms 70992 KB Output is correct
7 Correct 10 ms 71248 KB Output is correct
8 Correct 9 ms 70992 KB Output is correct
9 Correct 9 ms 70992 KB Output is correct
10 Correct 10 ms 71260 KB Output is correct
11 Correct 9 ms 71248 KB Output is correct
12 Correct 11 ms 71248 KB Output is correct
13 Correct 9 ms 71248 KB Output is correct
14 Correct 9 ms 70992 KB Output is correct
15 Correct 97 ms 71248 KB Output is correct
16 Correct 17 ms 71252 KB Output is correct
17 Correct 35 ms 71384 KB Output is correct
18 Correct 37 ms 71252 KB Output is correct
19 Correct 119 ms 71432 KB Output is correct
20 Correct 101 ms 71392 KB Output is correct
21 Correct 75 ms 71396 KB Output is correct
22 Correct 64 ms 71252 KB Output is correct
23 Correct 18 ms 71252 KB Output is correct
24 Correct 178 ms 71252 KB Output is correct
25 Correct 128 ms 71252 KB Output is correct
26 Correct 146 ms 71536 KB Output is correct
27 Correct 171 ms 71252 KB Output is correct