Submission #960883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960883	2024-04-11T07:22:50 Z	Ice_man	Tents (JOI18_tents)	C++14	100 / 100	41 ms	71016 KB

tents

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
//#include <vector>

#define maxn 3005
#define maxlog 20
#define INF 1000000010
#define mod 1000000007
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

///#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
///#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}

long long dp[maxn][maxn];
int n, m;


void read()
{
    cin >> n >> m;
}

void calc_dp()
{
    for(int i = 0;  i <= max(n , m); i++)
    {
        dp[i][0] = 1;
        dp[0][i] = 1;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] += dp[i - 1][j];
            dp[i][j] += dp[i - 1][j - 1] * j * 4LL;

            if(j > 1)
                dp[i][j] += dp[i - 1][j - 2] * (j - 1) * j / 2LL;

            if(i > 1)
                dp[i][j] += j * (i - 1) * dp[i - 2][j - 1];
            dp[i][j] %= mod;
        }
    cout << (dp[n][m] + mod - 1) % mod << endl;
}

int main()
{

    /**#ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();

    read();
    calc_dp();


    return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	2 ms	8540 KB	Output is correct
11	Correct	1 ms	8536 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	2 ms	8540 KB	Output is correct
11	Correct	1 ms	8536 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct
13	Correct	5 ms	43356 KB	Output is correct
14	Correct	9 ms	55900 KB	Output is correct
15	Correct	30 ms	66140 KB	Output is correct
16	Correct	6 ms	37468 KB	Output is correct
17	Correct	9 ms	43612 KB	Output is correct
18	Correct	9 ms	33408 KB	Output is correct
19	Correct	31 ms	70408 KB	Output is correct
20	Correct	23 ms	57944 KB	Output is correct
21	Correct	20 ms	49752 KB	Output is correct
22	Correct	17 ms	51700 KB	Output is correct
23	Correct	15 ms	70420 KB	Output is correct
24	Correct	39 ms	71016 KB	Output is correct
25	Correct	34 ms	62180 KB	Output is correct
26	Correct	37 ms	68336 KB	Output is correct
27	Correct	41 ms	70216 KB	Output is correct