oj.uz

Submission #127531

# Submission time Handle Problem Language Result Execution time Memory
127531 2019-07-09T13:49:53 Z BThero Tents (JOI18_tents) C++17
100 / 100
 174 ms 35704 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)3e3 + 5;

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

void solve() {
    scanf("%d %d", &n, &m);
    
    dp[0][m] = 1;

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

            if (j > 0) {
                dp[i + 2][j - 1] = addMod(dp[i + 2][j - 1], mulMod(dp[i][j], mulMod(j, n - i - 1)));
                dp[i + 1][j - 1] = addMod(dp[i + 1][j - 1], mulMod(4, mulMod(dp[i][j], j)));
            }

            if (j > 1) {
                dp[i + 1][j - 2] = addMod(dp[i + 1][j - 2], mulMod(dp[i][j], ways[j]));
            }
        }
    }

    int ans = MOD - 1;

    for (int i = 0; i <= m; ++i) {
        ans = addMod(ans, dp[n][i]);
    }

    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 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 4 ms 1400 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 4 ms 1656 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 1912 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 4 ms 1400 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 4 ms 1656 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 1912 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 13 ms 9592 KB Output is correct
15 Correct 121 ms 32892 KB Output is correct
16 Correct 10 ms 2680 KB Output is correct
17 Correct 29 ms 8056 KB Output is correct
18 Correct 40 ms 11000 KB Output is correct
19 Correct 136 ms 34552 KB Output is correct
20 Correct 111 ms 29176 KB Output is correct
21 Correct 74 ms 19832 KB Output is correct
22 Correct 76 ms 22264 KB Output is correct
23 Correct 52 ms 19752 KB Output is correct
24 Correct 174 ms 35704 KB Output is correct
25 Correct 135 ms 30840 KB Output is correct
26 Correct 154 ms 33576 KB Output is correct
27 Correct 168 ms 34680 KB Output is correct