oj.uz

Submission #651562

# Submission time Handle Problem Language Result Execution time Memory
651562 2022-10-19T10:46:50 Z shmad Tents (JOI18_tents) C++17
100 / 100
 155 ms 70776 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

//#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvt = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;

ll add (ll a, ll b) {
	a += b;
	if (a < 0) a += mod;
	if (a >= mod) a -= mod;
	return a;
}

ll mul (ll a, ll b) {
	a *= b;
	if (a >= mod) a %= mod;
	return a;
}

ll bp (ll n, ll k) {
	ll res = 1;
	while (k) {
	 	if (k & 1) res = mul(res, n);
	 	n = mul(n, n);
	 	k >>= 1;
	}
	return res;
}

int h, w;
ll dp[3005][3005];

void solve () {
	cin >> h >> w;
	dp[0][0] = 1;
	for (int i = 0; i <= 3000; i++) dp[i][0] = dp[0][i] = 1;
	ll inv2 = bp(2, mod - 2);
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {      
			dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - 1], mul(j, 4)));
			dp[i][j] = add(dp[i][j], dp[i - 1][j]);
			if (i >= 2) dp[i][j] = add(dp[i][j], mul(dp[i - 2][j - 1], mul(j, (i - 1))));
			if (j >= 2) dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - 2], mul(mul(j, (j - 1)), inv2)));
        }
	}
	dp[h][w] = add(dp[h][w], -1);
	cout << dp[h][w];
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12372 KB Output is correct
2 Correct 5 ms 12368 KB Output is correct
3 Correct 5 ms 12372 KB Output is correct
4 Correct 5 ms 12364 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12548 KB Output is correct
7 Correct 5 ms 12528 KB Output is correct
8 Correct 5 ms 12488 KB Output is correct
9 Correct 7 ms 12376 KB Output is correct
10 Correct 7 ms 12756 KB Output is correct
11 Correct 7 ms 12508 KB Output is correct
12 Correct 7 ms 13140 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12372 KB Output is correct
2 Correct 5 ms 12368 KB Output is correct
3 Correct 5 ms 12372 KB Output is correct
4 Correct 5 ms 12364 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12548 KB Output is correct
7 Correct 5 ms 12528 KB Output is correct
8 Correct 5 ms 12488 KB Output is correct
9 Correct 7 ms 12376 KB Output is correct
10 Correct 7 ms 12756 KB Output is correct
11 Correct 7 ms 12508 KB Output is correct
12 Correct 7 ms 13140 KB Output is correct
13 Correct 5 ms 12484 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 103 ms 56140 KB Output is correct
16 Correct 14 ms 15188 KB Output is correct
17 Correct 27 ms 22160 KB Output is correct
18 Correct 32 ms 24500 KB Output is correct
19 Correct 126 ms 63252 KB Output is correct
20 Correct 111 ms 53032 KB Output is correct
21 Correct 68 ms 39216 KB Output is correct
22 Correct 66 ms 38828 KB Output is correct
23 Correct 43 ms 27000 KB Output is correct
24 Correct 155 ms 70776 KB Output is correct
25 Correct 119 ms 62912 KB Output is correct
26 Correct 130 ms 67256 KB Output is correct
27 Correct 146 ms 69312 KB Output is correct