oj.uz

Submission #375686

# Submission time Handle Problem Language Result Execution time Memory
375686 2021-03-09T16:53:51 Z pit4h Tents (JOI18_tents) C++14
100 / 100
 265 ms 117356 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
const ll mod = 1e9+7, inv2 = (mod+1)/2;
const int MAXH = 3001;
ll factorial[MAXH], C[MAXH][MAXH];

ll fpow(ll x, ll p) {
	if(p==0LL) return 1LL;
	ll y = fpow(x, p/2);
	if(p%2==0) {
		return y*y % mod;	
	}
	return y*y % mod * x % mod;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int H, W; cin>>H>>W;

	factorial[0] = 1;
	for(int i=1; i<=max(H, W); ++i) {
		factorial[i] = factorial[i-1] * i % mod;
	}
	C[0][0] = 1;	
	for(int i=1; i<=max(H, W); ++i) {
		C[i][0] = C[i][i] = 1;
		for(int j=1; j<i; ++j) {
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}

	vector<vector<ll>> dp(H+1, vector<ll>(W+1));
	dp[0][0] = 1;

	for(int i=1; i<=H; ++i) {
		dp[i][0] = 1;
		for(int j=1; j<=W; ++j) {
			dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * (W - (j-1)) % mod * 4 % mod) % mod;

			if(i>=2) { //column
				dp[i][j] = (dp[i][j] + dp[i-2][j-1] * (H-(i-1)) % mod * (W-(j-1)) % mod) % mod;	
			}
			if(j>=2) { //row
				dp[i][j] = (dp[i][j] + dp[i-1][j-2] * ((W-(j-2)) * (W-(j-1)) / 2) % mod) % mod;
			}
		}
	}

	ll ans = 0;
	for(int j=1; j<=W; ++j) {
		ans = (ans + dp[H][j]) % mod;
	}
	cout<<ans<<'\n';
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 1388 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 2 ms 1644 KB Output is correct
8 Correct 2 ms 1772 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 3 ms 2156 KB Output is correct
11 Correct 1 ms 1900 KB Output is correct
12 Correct 4 ms 2668 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 1388 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 2 ms 1644 KB Output is correct
8 Correct 2 ms 1772 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 3 ms 2156 KB Output is correct
11 Correct 1 ms 1900 KB Output is correct
12 Correct 4 ms 2668 KB Output is correct
13 Correct 13 ms 21100 KB Output is correct
14 Correct 22 ms 30572 KB Output is correct
15 Correct 166 ms 84972 KB Output is correct
16 Correct 18 ms 18924 KB Output is correct
17 Correct 43 ms 30188 KB Output is correct
18 Correct 47 ms 24940 KB Output is correct
19 Correct 186 ms 95780 KB Output is correct
20 Correct 150 ms 74604 KB Output is correct
21 Correct 98 ms 52460 KB Output is correct
22 Correct 99 ms 53996 KB Output is correct
23 Correct 73 ms 61420 KB Output is correct
24 Correct 265 ms 117356 KB Output is correct
25 Correct 182 ms 89452 KB Output is correct
26 Correct 207 ms 102636 KB Output is correct
27 Correct 246 ms 113804 KB Output is correct