Submission #1282392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282392		KickingKun	Tents (JOI18_tents)	C++20	100 / 100	321 ms	106164 KiB

tents

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 3e3 + 5, lim = 60, mod = 1e9 + 7;
const ll INF = 1e18;

void add(int &a, int b) {
	if ((a += b) >= mod) a -= mod;
}

int dp[N][N];

int C2(int n) {
	return n * (n - 1) / 2;
}

namespace sub2 {
	int get_dp(int n, int m) {
		if (n < 0 || m < 0) return 0;
		if (n == 0 || m == 0) return 1;

		if (n > m) swap(n, m);
		if (dp[n][m] > 0) return dp[n][m];

		int &res = dp[n][m]; res = 1;
		for (int c = 1; c <= m; c++) { // co dinh cot dau tien dat
			// put W
			add(res, 1ll * get_dp(n - 1, m - c) * n % mod);
			// put E
			add(res, 1ll * get_dp(n - 1, m - c) * n % mod);
			add(res, 1ll * get_dp(n - 1, m - c - 1) * (m - c) % mod * n % mod);
			// put N
			add(res, 1ll * get_dp(n - 1, m - c) * n % mod);
			// put S
			add(res, 1ll * get_dp(n - 1, m - c) * n % mod);
			add(res, 1ll * get_dp(n - 2, m - c) * C2(n) % mod);
		}
		return res;
	}

	void solve(int n, int m) {
		cout << (get_dp(n, m) - 1 + mod) % mod;
	}
}

namespace sub3 {
	int sumF[N][N], polyF[N][N];

	int sum_dp(int n, int l, int r) {
		if (n < 0 || r < 0) return 0;
		if (l == 0) return sumF[n][r];
		int res = sumF[n][r] - sumF[n][l - 1];
		if (res < 0) res += mod;
		return res;
	}

	int poly_dp(int n, int l, int r) {
		if (n < 0 || r < 0) return 0;
		if (l == 0) return polyF[n][r];
		int res = polyF[n][r] - polyF[n][l - 1];
		if (res < 0) res += mod;
		return res;
	}

	void solve(int n, int m) {
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				if (i == 0 || j == 0) dp[i][j] = 1;
				else {
					dp[i][j] = 1;
					add(dp[i][j], 1ll * sum_dp(i - 1, 0, j - 1) * i * 4 % mod);
					add(dp[i][j], 1ll * poly_dp(i - 1, 0, j - 2) * i % mod);
					add(dp[i][j], 1ll * sum_dp(i - 2, 0, j - 1) * C2(i) % mod);
				}
			}
			sumF[i][0] = polyF[i][0] = dp[i][0];
			for (int j = 1; j <= m; j++) {
				sumF[i][j] = sumF[i][j - 1]; 
				polyF[i][j] = polyF[i][j - 1];
				add(sumF[i][j], dp[i][j]);
				add(polyF[i][j], 1ll * dp[i][j] * (j + 1) % mod);
			}
		}
		cout << (dp[n][m] - 1 + mod) % mod;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	int n, m; cin >> n >> m;
	if (max(n, m) <= 300) sub2::solve(n, m);
	else sub3::solve(n, m);
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:114:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:115:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52