Submission #1116880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116880		byebye75	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	271 ms	13568 KiB

ruins3

#include <iostream>

const long long M=605,mod=1e9+7;
int n,a[M];
long long C[2*M][2*M],F[M],dp[M][M];

int main(){
	C[0][0]=F[0]=dp[0][0]=1;
	for(int i=0;i<2*M-1;i++) for(int j=0;j<=i;j++){
		(C[i+1][j]+=C[i][j])%=mod;
		(C[i+1][j+1]+=C[i][j])%=mod;
	}
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",a+i);
	for(int i=0;i<n;i++) for(int j=0;j<=n;j++) if(dp[i][j]) for(int k=0;k<=std::min(n,a[i]-i-1)-j;k++){
		(dp[i+1][j+k]+=dp[i][j]*C[2*k][k]%mod*C[a[i]-i-j-1][k]%mod*F[k]%mod*(k?1:j-i))%=mod;
	}
	long long res=dp[n][n];
	for(int i=0;i<n;i++) (res*=mod/2+1)%=mod;
	printf("%lld\n",res);
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
ruins3.cpp:15:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  for(int i=0;i<n;i++) scanf("%d",a+i);
      |                       ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42