oj.uz

Submission #127433

# Submission time Handle Problem Language Result Execution time Memory
127433 2019-07-09T11:20:18 Z BThero Tents (JOI18_tents) C++17
48 / 100
 2000 ms 67576 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MOD = (int)1e9 + 7;
const int MAXN = (int)5e3 + 5;

int C[MAXN][MAXN];

int R[MAXN][MAXN];

int fact[MAXN];

int dp[MAXN];

int n, m;

int addMod(int a, int b, int m = MOD) {
    a += b;

    if (m <= a) {
        a -= m;
    }

    return a;
}

int mulMod(int a, int b, int m = MOD) {
    return a * 1ll * b % m;
}

int binPow(int a, int b, int m = MOD) {
    int ret = 1;

    while (b > 0) {
        if (b & 1) {
            ret = mulMod(ret, a, m);
        }

        a = mulMod(a, a, m);
        b >>= 1;
    }

    return ret;
}

void pre() {
    fact[0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        fact[i] = mulMod(fact[i - 1], i);
    }

    C[0][0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        C[i][0] = C[i - 1][0];

        for (int j = 1; j <= i; ++j) {
            C[i][j] = addMod(C[i - 1][j - 1], C[i - 1][j]);
        }
    }

    dp[0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        dp[i] = mulMod(dp[i - 1], i);
        dp[i] = mulMod(dp[i], 2 * i - 1);
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    int ans = MOD - 1;

    for (int a = 0; a <= m; ++a) {
        for (int b = 0; b <= m; ++b) {
            for (int c = 0; c <= m; ++c) {
                if (a + b + c * 2 <= m && a + 2 * b + c <= n) {
                    int cur = binPow(4, a);

                    cur = mulMod(cur, C[n][2 * b]);
                    cur = mulMod(cur, dp[b]);
                    cur = mulMod(cur, C[n - 2 * b][c]);
                    cur = mulMod(cur, C[n - c - 2 * b][a]);
                    cur = mulMod(cur, C[m][2 * c]);
                    cur = mulMod(cur, dp[c]);
                    cur = mulMod(cur, C[m - 2 * c][b]);
                    cur = mulMod(cur, C[m - 2 * c - b][a]);
                    cur = mulMod(cur, fact[a]);

                    ans = addMod(ans, cur);
                }
            }
        }
    }

    printf("%d\n", ans);
}

int main() {
    int tt = 1;

    pre();

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message

tents.cpp: In function 'void solve()':
tents.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 67448 KB Output is correct
2 Correct 72 ms 67448 KB Output is correct
3 Correct 66 ms 67368 KB Output is correct
4 Correct 68 ms 67424 KB Output is correct
5 Correct 84 ms 67400 KB Output is correct
6 Correct 72 ms 67448 KB Output is correct
7 Correct 81 ms 67576 KB Output is correct
8 Correct 68 ms 67448 KB Output is correct
9 Correct 66 ms 67448 KB Output is correct
10 Correct 86 ms 67448 KB Output is correct
11 Correct 93 ms 67548 KB Output is correct
12 Correct 213 ms 67548 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 67448 KB Output is correct
2 Correct 72 ms 67448 KB Output is correct
3 Correct 66 ms 67368 KB Output is correct
4 Correct 68 ms 67424 KB Output is correct
5 Correct 84 ms 67400 KB Output is correct
6 Correct 72 ms 67448 KB Output is correct
7 Correct 81 ms 67576 KB Output is correct
8 Correct 68 ms 67448 KB Output is correct
9 Correct 66 ms 67448 KB Output is correct
10 Correct 86 ms 67448 KB Output is correct
11 Correct 93 ms 67548 KB Output is correct
12 Correct 213 ms 67548 KB Output is correct
13 Execution timed out 2051 ms 67420 KB Time limit exceeded
14 Halted 0 ms 0 KB -