oj.uz

Submission #127344

# Submission time Handle Problem Language Result Execution time Memory
127344 2019-07-09T08:57:36 Z BThero Tents (JOI18_tents) C++17
48 / 100
 277 ms 1560 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 = 500 + 5;

int dp[2][MAXN][MAXN];

int ways[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() {
    for (int i = 2; i < MAXN; ++i) {
        if (i & 1) {
            ways[i] = mulMod(i, (i - 1) / 2);
        }
        else {
            ways[i] = mulMod(i / 2, i - 1);
        }
    }
}

void solve() {
    scanf("%d %d", &n, &m);

    dp[0][0][m] = 1;
    dp[0][1][m - 1] = m;

    if (m > 1) {
        dp[0][0][m - 2] = ways[m];
    }

    for (int i = 2; i <= n; ++i) {
        for (int a = 0; a <= m; ++a) {
            for (int b = 0; b <= m; ++b) {
                dp[1][a][b] = addMod(dp[1][a][b], dp[0][a][b]);

                if (a > 0) {
                    dp[1][a - 1][b] = addMod(dp[1][a - 1][b], mulMod(a, dp[0][a][b]));
                }

                if (b > 0) {
                    dp[1][a + 1][b - 1] = addMod(dp[1][a + 1][b - 1], mulMod(b, dp[0][a][b]));
                }

                if (b > 1) {
                    dp[1][a][b - 2] = addMod(dp[1][a][b - 2], mulMod(dp[0][a][b], ways[b]));
                }
            }
        }

        for (int a = 0; a <= m; ++a) {
            for (int b = 0; b <= m; ++b) {
                dp[0][a][b] = dp[1][a][b];
                dp[1][a][b] = 0;
            }
        }
    }

    int ans = MOD - 1;

    for (int a = 0, cur = 1; a <= m; ++a) {
        for (int b = 0; b <= m; ++b) {
            ans = addMod(ans, mulMod(dp[0][a][b], cur));
        }

        cur = mulMod(cur, 4);
    }

    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:75: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 2 ms 376 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 44 ms 1400 KB Output is correct
6 Correct 20 ms 752 KB Output is correct
7 Correct 48 ms 1172 KB Output is correct
8 Correct 11 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 61 ms 888 KB Output is correct
11 Correct 12 ms 1528 KB Output is correct
12 Correct 277 ms 1560 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 44 ms 1400 KB Output is correct
6 Correct 20 ms 752 KB Output is correct
7 Correct 48 ms 1172 KB Output is correct
8 Correct 11 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 61 ms 888 KB Output is correct
11 Correct 12 ms 1528 KB Output is correct
12 Correct 277 ms 1560 KB Output is correct
13 Runtime error 8 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -