Submission #1184374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184374		catch_me_if_you_can	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	76 ms	55876 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int INF = 1e9;
const int MX = 103;
const int LMX = 1003;
const int mod = 1e9+7;

array<int, 3> dp[MX][MX][LMX];

signed main()
{
	fast();
	int n, L; cin >> n >> L;
	//vector<int> b(n);
	vector<int> a(n+2); a[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		//b[i-1] = a[i];
	}
	/*int sp = 1;
	for(int i = 1; i <= n; i++)
		sp*=i;
	int CNT = 0;
	while(sp--)
	{
		int ok = 0;
		for(int i = 1; i < n; i++)
			ok+=abs(b[i]-b[i-1]);
		if(ok <= L)
			CNT++;
		next_permutation(b.begin(), b.end());
	}*/
	a[n+1] = INF;
	sort(a.begin(), a.end());
	dp[1][1][0] = {1, (n >= 2)? 2 : 0, (n >= 3)? 1 : 0};
	for(int i = 1; i <= n; i++)
	{
		for(int c = 0; c < 3; c++)
		{
			for(int j = 1; (j <= i) && (((i+j-1)+c) <= n); j++)
			{
				for(int M = 0; M <= L; M++)
				{	
					//Case 1: After inserting number of comp is same.
					int UP = ((2*j-2) + c)*(a[i+1]-a[i]);
					if((M+UP) > L)
						continue;
					//Case 1.1: We add to an end point.
					if(c)
					{
						dp[i+1][j][M+UP][c-1]+=(dp[i][j][M][c]*c);
						dp[i+1][j][M+UP][c-1]%=mod;
					}
					//Case 1.2: We do not add to an endpoint
					dp[i+1][j][M+UP][c]+=(((dp[i][j][M][c]*(2*j-2+c)))%mod);
					dp[i+1][j][M+UP][c]%=mod;
					//Case 2. After inserting, number of components INCREASEs. (sole component)
					//Case 2.1 We add to an end point.
					if(c)
					{
						dp[i+1][j+1][M+UP][c-1]+=((dp[i][j][M][c])*c);
						dp[i+1][j+1][M+UP][c-1]%=mod;
					}
					//Case 2.2 We do not add to an endpoint
					dp[i+1][j+1][M+UP][c]+=((dp[i][j][M][c]*(j-1+c))%mod);
					dp[i+1][j+1][M+UP][c]%=mod;
					//Case 3. After inserting, number of components DECREASEs. (by 1 ofc)
					//(this can ONLY happen when two components are merged, in particular c is untouched)
					if(j)
					{
						dp[i+1][j-1][M+UP][c]+=((dp[i][j][M][c]*(j-1))%mod);
						dp[i+1][j-1][M+UP][c]%=mod;	
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= L; i++)
		ans+=dp[n][1][i][0];
	ans%=mod;
	//assert(CNT == ans);
	cout << ans << "\n";
	return 0;
}	

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