Submission #257676

#	Time	Username	Problem	Language	Result	Execution time	Memory
257676		TadijaSebez	Ruins 3 (JOI20_ruins3)	C++11	100 / 100	1116 ms	2040 KiB

ruins3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int mul(int x,int y){return (ll)x*y%mod;}
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
void ckadd(int&x,int y){x=add(x,y);}
const int N=605;
const int M=N*2;
int F[M],I[M],a[N],dp[N][N];
int binom(int n,int k){return mul(F[n],mul(I[k],I[n-k]));}
int main(){
	F[0]=1;for(int i=1;i<M;i++)F[i]=mul(F[i-1],i);
	I[1]=1;for(int i=2;i<M;i++)I[i]=mul(sub(mod,mod/i),I[mod%i]);
	I[0]=1;for(int i=2;i<M;i++)I[i]=mul(I[i],I[i-1]);
	int n;scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=a[i]-i;j++){
			dp[i][j]=mul(dp[i-1][j],j-i+1);
			for(int k=1;k<=j;k++){
				ckadd(dp[i][j],mul(binom(k*2,k),mul(binom(a[i]-i-j+k,k),mul(F[k],dp[i-1][j-k]))));
			}
		}
	}
	int ans=dp[n][n];
	for(int i=1;i<=n;i++)ans=mul(ans,(mod+1)/2);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

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

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