Submission #1193924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193924		MuhammadSaram	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	181 ms	164996 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7, M = 105, MAXL = 1005;

int dp[M][M][MAXL][4]; 

signed main()
{
	int n,l;
	cin>>n>>l;
	int a[n+1];
	for (int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	dp[1][1][0][0]=1;
	dp[1][1][0][1]=2;
	dp[1][1][0][2]=1;
	for (int i=2;i<=n;i++)
		for (int j=1;j<=n;j++)
			for (int k=0;k<=2;k++)
			{
				int cst=(a[i]-a[i-1])*(2*j-k);
				for (int p=cst;p<=l;p++)
				{
					dp[i][j+1][p][k]=(dp[i-1][j][p-cst][k]*(j+1-k)+dp[i][j+1][p][k])%mod;
					dp[i][j+1][p][k+1]=(dp[i-1][j][p-cst][k]*(2-k)+dp[i][j+1][p][k+1])%mod;
					dp[i][j][p][k]=(dp[i-1][j][p-cst][k]*(2*j-k)+dp[i][j][p][k])%mod;
					dp[i][j][p][k+1]=(dp[i-1][j][p-cst][k]*(2-k)+dp[i][j][p][k+1])%mod;
					dp[i][j-1][p][k]=(dp[i-1][j][p-cst][k]*(j-1)+dp[i][j-1][p][k])%mod;
				}
			}
	int ans=0;
	for (int i=0;i<=l;i++)
		ans=(ans+dp[n][1][i][2])%mod;
	cout<<ans<<endl;
	
	return 0;
}

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