oj.uz

Submission #516224

# Submission time Handle Problem Language Result Execution time Memory
516224 2022-01-20T17:07:05 Z angelo_torres Tents (JOI18_tents) C++17
100 / 100
 216 ms 117568 KB 
#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define fr(i,j,n) for(ll i = j; i >= n; --i)
#define sz(v) (int) v.size()
#define ff first
#define ss second
#define endl "\n"

using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int N = 3e3 + 20;
const int M = 35;
const int inf = 2e9;
const ll mod = 1e9 + 7;

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

ll sum(ll a,ll b){
	return (a+b)%mod;
}

ll h,w,dp[N][N],comb[N][N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> h >> w;
	comb[0][0] = 1;
	f(i,1,max(h,w)+1){
		f(j,0,i+1){
			comb[i][j] = 1;
			if(j == 0) continue;
			comb[i][j] = sum(comb[i-1][j],comb[i-1][j-1]);
		}
	}
	dp[0][0] = 1;
	f(i,1,h+1){
		f(j,1,w+1){
			ll nj = (j*(j-1))>>1;
			nj %= mod;
			dp[i][j] = sum(dp[i][j],mul(4,mul(j,dp[i-1][j-1])));
			if(j > 1) dp[i][j] = sum(dp[i][j],mul(nj,dp[i-1][j-2]));
			if(i > 1) dp[i][j] = sum(dp[i][j],mul(mul(j,i-1),dp[i-2][j-1]));
			// cout << dp[i][j] << " ";
		}
		// cout << endl;
	}
	ll ans = 0;
	f(i,1,h+1){
		f(j,1,w+1) ans = sum(ans,mul(mul(comb[h][i],comb[w][j]),dp[i][j]));
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 1136 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 2508 KB Output is correct
7 Correct 2 ms 1856 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 2 ms 3268 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 4 ms 3776 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 1136 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 2508 KB Output is correct
7 Correct 2 ms 1856 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 2 ms 3268 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 4 ms 3776 KB Output is correct
13 Correct 11 ms 20920 KB Output is correct
14 Correct 22 ms 39612 KB Output is correct
15 Correct 169 ms 95872 KB Output is correct
16 Correct 17 ms 19752 KB Output is correct
17 Correct 40 ms 32744 KB Output is correct
18 Correct 46 ms 29456 KB Output is correct
19 Correct 173 ms 107068 KB Output is correct
20 Correct 138 ms 84160 KB Output is correct
21 Correct 105 ms 58936 KB Output is correct
22 Correct 103 ms 62336 KB Output is correct
23 Correct 74 ms 73376 KB Output is correct
24 Correct 216 ms 117568 KB Output is correct
25 Correct 183 ms 98160 KB Output is correct
26 Correct 189 ms 109012 KB Output is correct
27 Correct 215 ms 114696 KB Output is correct