Submission #67267

#	Time	Username	Problem	Language	Result	Execution time	Memory
67267		kingpig9	Tents (JOI18_tents)	C++11	100 / 100	146 ms	36036 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3018, MOD = 1e9 + 7;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void addeq (int &x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

int mult (int x, int y) {
	return ll(x) * y % MOD;
}

int N, M;
int dp[MAXN][MAXN];

int main() {
	scanf("%d %d", &N, &M);
	for (int j = 0; j <= M; j++) {
		dp[0][j] = 1;
	}
	for (int i = 0; i <= N; i++) {
		dp[i][0] = 1;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			int &ref = dp[i][j];

			addeq(ref, mult(4 * j, dp[i - 1][j - 1]));	//put one on this row
			addeq(ref, dp[i - 1][j]);	//put nothing on this row

			if (j > 1) {
				addeq(ref, mult(j * (j - 1) / 2, dp[i - 1][j - 2]));	//2 points on the same row
			}
			if (i > 1) {
				addeq(ref, mult((i - 1) * j, dp[i - 2][j - 1]));
			}
		}
	}
	printf("%d\n", dp[N][M] - 1);
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:31:7: 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