oj.uz

Submission #388531

# Submission time Handle Problem Language Result Execution time Memory
388531 2021-04-12T02:03:59 Z nathanlee726 Tents (JOI18_tents) C++14
100 / 100
 122 ms 71016 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int dp[3005][3005];
signed main(){
	IOS();
	int n,m;
	cin>>n>>m;
	F(max(n,m)+1)dp[0][i]=dp[i][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i][j-1];
			dp[i][j]=add(dp[i][j],(4ll*i*dp[i-1][j-1])%mod);
			dp[i][j]=add(dp[i][j],(i*(j-1)*dp[i-1][max(j-2,0ll)])%mod);
			dp[i][j]=add(dp[i][j],(i*(i-1)/2*dp[max(i-2,0ll)][j-1])%mod);
		}
	}
	cout<<sub(dp[n][m],1)<<endl;
	return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 2 ms 1356 KB Output is correct
8 Correct 1 ms 1348 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 2 ms 2128 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 2 ms 1356 KB Output is correct
8 Correct 1 ms 1348 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 2 ms 2128 KB Output is correct
13 Correct 4 ms 7748 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 81 ms 55124 KB Output is correct
16 Correct 8 ms 9396 KB Output is correct
17 Correct 20 ms 17356 KB Output is correct
18 Correct 27 ms 17704 KB Output is correct
19 Correct 90 ms 63044 KB Output is correct
20 Correct 73 ms 50832 KB Output is correct
21 Correct 49 ms 35392 KB Output is correct
22 Correct 50 ms 35472 KB Output is correct
23 Correct 31 ms 26972 KB Output is correct
24 Correct 122 ms 71016 KB Output is correct
25 Correct 94 ms 61204 KB Output is correct
26 Correct 104 ms 66564 KB Output is correct
27 Correct 115 ms 69104 KB Output is correct