Submission #1313419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313419		boclobanchat	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	282 ms	28996 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
const long long mod=1e9+7;
long long dp[MAXN][MAXN][1024][2][2],A[MAXN],fr[MAXN*2],inv[MAXN*2],f1[MAXN][MAXN][2],f3[MAXN][MAXN][2],f5[MAXN][MAXN][2];
long long poww(long long n,long long m)
{
	long long res=n,ans=1;
	while(m)
	{
		if(m&1) ans=ans*res%mod;
		res=res*res%mod,m/=2;
	}
	return ans;
}
long long icandy(int n,int k)
{
	return inv[n-1]*fr[n-k]%mod*fr[k-1]%mod;
}
long long candy(int n,int k)
{
	return fr[n-1]*inv[n-k]%mod*inv[k-1]%mod;
}
void add(long long& a,long long b)
{
	if((a+=b)>=mod) a-=mod;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	fr[0]=inv[0]=1;
	for(int i=1;i<=n*2;i++) inv[i]=poww(fr[i]=fr[i-1]*i%mod,mod-2);
	for(int i=1;i<=n;i++) cin>>A[i];
	sort(A+1,A+n+1);
	f1[0][0][0]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<j;k++) 
	{
		add(f1[i][j][0],f1[i-1][k][0]);
		add(f1[i][j][1],f1[i-1][k][1]);
		if(j-k>1) add(f1[i][j][1],f1[i-1][k][0]*(j-k-2)%mod);
	}
	f3[0][0][0]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<j;k++) 
	{
		add(f3[i][j][0],f3[i-1][k][0]);
		add(f3[i][j][1],f3[i-1][k][1]);
		if(j-k>1) add(f3[i][j][1],f3[i-1][k][0]*2%mod);
	}
	f5[0][0][0]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<j;k++) 
	{
		add(f5[i][j][0],f5[i-1][k][0]);
		add(f5[i][j][1],f5[i-1][k][1]);
		if(j-k==1) add(f5[i][j][1],f5[i-1][k][0]%mod);
	}
	dp[0][0][0][0][0]=1;
	for(int i=1;i<n;i++)
	{
		int d=A[i+1]-A[i];
		for(int j=0;j<=n;j++) for(int c=0;c<=k;c++) for(int p=0;p<2;p++) for(int q=0;q<2;q++)
		{
			long long res=dp[i-1][j][c][p][q]*icandy(n-i+1,j+1-p-q)%mod,nexc;
			if(!res) continue;
			nexc=c+(-p-q+(j+1)*2)*d;
			if(nexc>=c&&nexc<=k) add(dp[i][j+1][nexc][p][q],res*f1[j+1-p-q][n-i+1][1]%mod);
			nexc-=d;
			if(nexc>=c&&nexc<=k)
			{
				if(!p) add(dp[i][j+1][nexc][1][q],res*candy(n-i,j+1-p-q)%mod);
				if(!q) add(dp[i][j+1][nexc][p][1],res*candy(n-i,j+1-p-q)%mod);
			}
			nexc-=d;
			if(nexc>=c&&nexc<=k) add(dp[i][j][nexc][p][q],res*(f3[j+1-p-q][n-i+1][1]-candy(n-i,j+1-p-q)*(2-p-q)%mod+mod)%mod);
			nexc-=d;
			if(nexc>=c&&nexc<=k)
			{
				if(!p) add(dp[i][j][nexc][1][q],res*candy(n-i,j-p-q)%mod);
				if(!q) add(dp[i][j][nexc][p][1],res*candy(n-i,j-p-q)%mod);
			}
			nexc-=d;
			if(nexc>=c&&nexc<=k) add(dp[i][j-1][nexc][p][q],res*(f5[j+1-p-q][n-i+1][1]-candy(n-i,j-p-q)*(2-p-q)%mod+mod)%mod);
		}
	}
	long long ans=0;
	for(int i=0;i<=k;i++) for(int j=0;j<=2;j++) for(int p=0;p<2;p++) for(int q=0;q<2;q++) add(ans,dp[n-1][j][i][p][q]);
	cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80