oj.uz

Submission #850937

# Submission time Handle Problem Language Result Execution time Memory
850937 2023-09-17T23:35:59 Z Itamar NoM (RMI21_nom) C++14
100 / 100
 239 ms 188496 KB 
#include <iostream>
using namespace std;
#include <vector>
#define ll long long
#define pll pair<ll,ll>
#define vll vector<ll>

const int siz = 4001;
ll dp[siz][siz];
ll fac[siz];
ll c[siz][siz];
const int mod = 1e9 + 7;
int main()
{
    int n, m;
    cin >> n >> m;
    dp[0][0] = 1;
    fac[0] = 1;
    for (int i = 1; i < siz; i++) {
        fac[i] = (i * fac[i - 1]) % mod;
    }
    for (int i = 0; i < siz; i++) {
        for (int j = 0; j < siz; j++) {
            if (j == 0)c[i][j] = 1;
            else if (i == 0)c[i][j] = 0;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    for (int i = 1; i <= m; i++) {
        int pile = ((2 * n) / m) + (i <= (2 * n) % m);
        for (int j = 0; j <= 2 * n; j++) {
            for (int k = 0; k<=j && j+pile>=2*k&& k<=pile; k++) {
                dp[i][j] =(dp[i][j]+(((dp[i - 1][j + pile - 2 * k] * ((c[j + pile - 2 * k][j - k] * fac[pile - k]) % mod)) % mod)* c[pile][k]) % mod)%mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        dp[m][0]=(2*dp[m][0])%mod;
    }
    dp[m][0] = (dp[m][0] * fac[n]) % mod;
    cout << dp[m][0];

}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 125776 KB Output is correct
2 Correct 35 ms 125776 KB Output is correct
3 Correct 35 ms 125776 KB Output is correct
4 Correct 36 ms 125688 KB Output is correct
5 Correct 35 ms 125776 KB Output is correct
6 Correct 35 ms 125776 KB Output is correct
7 Correct 35 ms 125776 KB Output is correct
8 Correct 35 ms 125780 KB Output is correct
9 Correct 35 ms 125524 KB Output is correct
10 Correct 41 ms 125784 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 125776 KB Output is correct
2 Correct 35 ms 125776 KB Output is correct
3 Correct 35 ms 125776 KB Output is correct
4 Correct 36 ms 125688 KB Output is correct
5 Correct 35 ms 125776 KB Output is correct
6 Correct 35 ms 125776 KB Output is correct
7 Correct 35 ms 125776 KB Output is correct
8 Correct 35 ms 125780 KB Output is correct
9 Correct 35 ms 125524 KB Output is correct
10 Correct 41 ms 125784 KB Output is correct
11 Correct 36 ms 126032 KB Output is correct
12 Correct 35 ms 126032 KB Output is correct
13 Correct 35 ms 125744 KB Output is correct
14 Correct 35 ms 125864 KB Output is correct
15 Correct 35 ms 126032 KB Output is correct
16 Correct 35 ms 125704 KB Output is correct
17 Correct 35 ms 125780 KB Output is correct
18 Correct 35 ms 126024 KB Output is correct
19 Correct 35 ms 125604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 125776 KB Output is correct
2 Correct 35 ms 125776 KB Output is correct
3 Correct 35 ms 125776 KB Output is correct
4 Correct 36 ms 125688 KB Output is correct
5 Correct 35 ms 125776 KB Output is correct
6 Correct 35 ms 125776 KB Output is correct
7 Correct 35 ms 125776 KB Output is correct
8 Correct 35 ms 125780 KB Output is correct
9 Correct 35 ms 125524 KB Output is correct
10 Correct 41 ms 125784 KB Output is correct
11 Correct 36 ms 126032 KB Output is correct
12 Correct 35 ms 126032 KB Output is correct
13 Correct 35 ms 125744 KB Output is correct
14 Correct 35 ms 125864 KB Output is correct
15 Correct 35 ms 126032 KB Output is correct
16 Correct 35 ms 125704 KB Output is correct
17 Correct 35 ms 125780 KB Output is correct
18 Correct 35 ms 126024 KB Output is correct
19 Correct 35 ms 125604 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 37 ms 126188 KB Output is correct
22 Correct 39 ms 127828 KB Output is correct
23 Correct 39 ms 125776 KB Output is correct
24 Correct 38 ms 126832 KB Output is correct
25 Correct 40 ms 127732 KB Output is correct
26 Correct 37 ms 125776 KB Output is correct
27 Correct 41 ms 128592 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 125776 KB Output is correct
2 Correct 35 ms 125776 KB Output is correct
3 Correct 35 ms 125776 KB Output is correct
4 Correct 36 ms 125688 KB Output is correct
5 Correct 35 ms 125776 KB Output is correct
6 Correct 35 ms 125776 KB Output is correct
7 Correct 35 ms 125776 KB Output is correct
8 Correct 35 ms 125780 KB Output is correct
9 Correct 35 ms 125524 KB Output is correct
10 Correct 41 ms 125784 KB Output is correct
11 Correct 36 ms 126032 KB Output is correct
12 Correct 35 ms 126032 KB Output is correct
13 Correct 35 ms 125744 KB Output is correct
14 Correct 35 ms 125864 KB Output is correct
15 Correct 35 ms 126032 KB Output is correct
16 Correct 35 ms 125704 KB Output is correct
17 Correct 35 ms 125780 KB Output is correct
18 Correct 35 ms 126024 KB Output is correct
19 Correct 35 ms 125604 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 37 ms 126188 KB Output is correct
22 Correct 39 ms 127828 KB Output is correct
23 Correct 39 ms 125776 KB Output is correct
24 Correct 38 ms 126832 KB Output is correct
25 Correct 40 ms 127732 KB Output is correct
26 Correct 37 ms 125776 KB Output is correct
27 Correct 41 ms 128592 KB Output is correct
28 Correct 47 ms 125888 KB Output is correct
29 Correct 52 ms 130384 KB Output is correct
30 Correct 56 ms 133968 KB Output is correct
31 Correct 46 ms 125776 KB Output is correct
32 Correct 53 ms 130640 KB Output is correct
33 Correct 59 ms 135504 KB Output is correct
34 Correct 77 ms 141856 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 125776 KB Output is correct
2 Correct 35 ms 125776 KB Output is correct
3 Correct 35 ms 125776 KB Output is correct
4 Correct 36 ms 125688 KB Output is correct
5 Correct 35 ms 125776 KB Output is correct
6 Correct 35 ms 125776 KB Output is correct
7 Correct 35 ms 125776 KB Output is correct
8 Correct 35 ms 125780 KB Output is correct
9 Correct 35 ms 125524 KB Output is correct
10 Correct 41 ms 125784 KB Output is correct
11 Correct 36 ms 126032 KB Output is correct
12 Correct 35 ms 126032 KB Output is correct
13 Correct 35 ms 125744 KB Output is correct
14 Correct 35 ms 125864 KB Output is correct
15 Correct 35 ms 126032 KB Output is correct
16 Correct 35 ms 125704 KB Output is correct
17 Correct 35 ms 125780 KB Output is correct
18 Correct 35 ms 126024 KB Output is correct
19 Correct 35 ms 125604 KB Output is correct
20 Correct 37 ms 125776 KB Output is correct
21 Correct 37 ms 126188 KB Output is correct
22 Correct 39 ms 127828 KB Output is correct
23 Correct 39 ms 125776 KB Output is correct
24 Correct 38 ms 126832 KB Output is correct
25 Correct 40 ms 127732 KB Output is correct
26 Correct 37 ms 125776 KB Output is correct
27 Correct 41 ms 128592 KB Output is correct
28 Correct 47 ms 125888 KB Output is correct
29 Correct 52 ms 130384 KB Output is correct
30 Correct 56 ms 133968 KB Output is correct
31 Correct 46 ms 125776 KB Output is correct
32 Correct 53 ms 130640 KB Output is correct
33 Correct 59 ms 135504 KB Output is correct
34 Correct 77 ms 141856 KB Output is correct
35 Correct 114 ms 126164 KB Output is correct
36 Correct 197 ms 178512 KB Output is correct
37 Correct 104 ms 126288 KB Output is correct
38 Correct 150 ms 150096 KB Output is correct
39 Correct 159 ms 168716 KB Output is correct
40 Correct 239 ms 188496 KB Output is correct