Submission #46431

#	Time	Username	Problem	Language	Result	Execution time	Memory
46431		chpipis	Tents (JOI18_tents)	C++11	100 / 100	112 ms	36028 KiB

tents

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MOD = 1e9 + 7;
const int MAXN = 3005;

inline int mul_mod(int a, int b) {
    return a * 1LL * b % MOD;
}

inline void add_mod(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

inline void sub_mod(int &a, int b) {
    a -= b;
    if (a < 0) a += MOD;
}

int dp[MAXN][MAXN];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++)
        dp[i][0] = 1;
    for (int j = 0; j <= m; j++)
        dp[0][j] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = mul_mod(dp[i - 1][j - 1], 4 * j);
            add_mod(dp[i][j], dp[i - 1][j]);
            if (j >= 2)
                add_mod(dp[i][j], mul_mod(j * (j - 1) / 2, dp[i - 1][j - 2]));
            if (i >= 2)
                add_mod(dp[i][j], mul_mod(j * (i - 1), dp[i - 2][j - 1]));
        }
    }
    sub_mod(dp[n][m], 1);
    printf("%d\n", dp[n][m]);
    return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:80: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 / 48
• Subtask 2: 52 / 52