oj.uz

Submission #595282

# Submission time Handle Problem Language Result Execution time Memory
595282 2022-07-13T14:21:37 Z Koosha_mv Ruins 3 (JOI20_ruins3) C++14
58 / 100
 6000 ms 11224 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=1205,mod=1e9+7,inv2=mod/2+1;

int n,t,f[N],g[N],fact[N],C[N][N],dp[N][N],mark[N];
vector<int> A,B;

ll pow(ll x,ll y,ll mod){return(!y?1:pow(x*x%mod,y/2,mod)*(y&1?x:1))%mod;}

int G(int n){
	if(n==0) return 1;
	return (C[n][2*n]-C[n-1][2*n]+mod)%mod;
}
int c(int k,int n){
	if(k<0 || k>n) return 0;
	return C[k][n];
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	fact[0]=1;
	f(i,0,N){
		C[0][i]=1;
		f(j,1,i+1) C[j][i]=(C[j-1][i-1]+C[j][i-1])%mod;
		if(i>0) fact[i]=1ll*fact[i-1]*i%mod;
	}
	g[1]=f[1]=1;
	f(i,2,N){
		f(j,0,i/2+1){
			int res=1ll*C[2*j][i]*G(j)%mod*pow(inv2,2*j,mod)%mod;
			res=1ll*res*fact[i]%mod*fact[i]%mod;
			Add(g[i],res);
		}
		f[i]=g[i];
		f(j,1,i){
			Add(f[i],mod-1ll*f[j]*g[i-j]%mod*C[j][i]%mod*C[j-1][i-1]%mod);
		}
	}
	//dbga(f,1,10);
	cin>>n;
	f(i,1,n+1){
		int x;
		cin>>x;
		mark[x]=1;
	}
	f(i,1,2*n+1){
		if(mark[i]) A.pb(i);
		else B.pb(i);
	}
	dp[0][0]=1;
	f(i,1,n+1){
		f(j,1,i+1){
			f(k,0,i){
				f(p,0,j){
					int x=lower_bound(all(B),A[j-1])-B.begin()-k;
					int res=1ll*dp[k][p]*c(i-k-1,(n+1-j)-(n-i)-1)%mod*f[i-k]%mod;
					res=1ll*res*c(i-k,x)%mod;
					Add(dp[i][j],res);
				}
			}
		//	cout<<i<<" "<<j<<" -> "<<dp[i][j]<<endl;
		}
	}
	int ans=0;
	f(i,1,n+1) Add(ans,dp[n][i]);
	cout<<ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9832 KB Output is correct
2 Correct 35 ms 9836 KB Output is correct
3 Correct 35 ms 9832 KB Output is correct
4 Correct 43 ms 9832 KB Output is correct
5 Correct 43 ms 9840 KB Output is correct
6 Correct 43 ms 9836 KB Output is correct
7 Correct 37 ms 9820 KB Output is correct
8 Correct 35 ms 9840 KB Output is correct
9 Correct 36 ms 9940 KB Output is correct
10 Correct 35 ms 9828 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9832 KB Output is correct
2 Correct 35 ms 9836 KB Output is correct
3 Correct 35 ms 9832 KB Output is correct
4 Correct 43 ms 9832 KB Output is correct
5 Correct 43 ms 9840 KB Output is correct
6 Correct 43 ms 9836 KB Output is correct
7 Correct 37 ms 9820 KB Output is correct
8 Correct 35 ms 9840 KB Output is correct
9 Correct 36 ms 9940 KB Output is correct
10 Correct 35 ms 9828 KB Output is correct
11 Correct 65 ms 10088 KB Output is correct
12 Correct 54 ms 10084 KB Output is correct
13 Correct 51 ms 10028 KB Output is correct
14 Correct 51 ms 10088 KB Output is correct
15 Correct 52 ms 10092 KB Output is correct
16 Correct 49 ms 10020 KB Output is correct
17 Correct 49 ms 10092 KB Output is correct
18 Correct 57 ms 10072 KB Output is correct
19 Correct 56 ms 10028 KB Output is correct
20 Correct 55 ms 10088 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9832 KB Output is correct
2 Correct 35 ms 9836 KB Output is correct
3 Correct 35 ms 9832 KB Output is correct
4 Correct 43 ms 9832 KB Output is correct
5 Correct 43 ms 9840 KB Output is correct
6 Correct 43 ms 9836 KB Output is correct
7 Correct 37 ms 9820 KB Output is correct
8 Correct 35 ms 9840 KB Output is correct
9 Correct 36 ms 9940 KB Output is correct
10 Correct 35 ms 9828 KB Output is correct
11 Correct 65 ms 10088 KB Output is correct
12 Correct 54 ms 10084 KB Output is correct
13 Correct 51 ms 10028 KB Output is correct
14 Correct 51 ms 10088 KB Output is correct
15 Correct 52 ms 10092 KB Output is correct
16 Correct 49 ms 10020 KB Output is correct
17 Correct 49 ms 10092 KB Output is correct
18 Correct 57 ms 10072 KB Output is correct
19 Correct 56 ms 10028 KB Output is correct
20 Correct 55 ms 10088 KB Output is correct
21 Execution timed out 6039 ms 11224 KB Time limit exceeded
22 Halted 0 ms 0 KB -