Submission #1285486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285486		Jawad_Akbar_JJ	Skyscraper (JOI16_skyscraper)	C++20	5 / 100	2 ms	844 KiB

skyscraper

#include <iostream>
#include <algorithm>

using namespace std;
#define int long long
const int N = 102, M = N * 10;
int dp[N][N][M][3], a[N], mod = 998244353, Ans, n, L;

signed main(){
	cin>>n>>L;

	for (int i=1;i<=n;i++)
		cin>>a[i];
	sort(a + 1, a + n + 1);

	a[n+1] =  10000;
	dp[0][0][0][0] = 1;

	for (int i=1;i<=n;i++){
		// cout<<a[i]<<endl;
		for (int j=1;j<=n;j++){
			for (int k=0;k<=L;k++){
				for (int m : {0, 1, 2}){
					int delta = (2 * j - m) * (a[i+1] - a[i]);
					if (k < delta or i + j + 1 - m > n)
						continue;

					// make an individual endpoint
					if (m)
						dp[i][j][k][m] += (3 - m) * dp[i-1][j-1][k - delta][m - 1];

					// make individual non-end component
					dp[i][j][k][m] += dp[i-1][j - 1][k - delta][m];
					// dp[i][j][k][m] += dp[i - 1][j - 1][k - cost_diff][m];

					// connect to an existing component
					dp[i][j][k][m] += (2 * j - m) * dp[i-1][j][k - delta][m];


					// connect to a component such that it becomes an endpoint
					if (m == 1)
						dp[i][j][k][m] += 2 * j * dp[i-1][j][k - delta][m - 1];
					else if (m == 2){
						if (i == n)
							dp[i][j][k][m] += dp[i-1][j][k - delta][m - 1];
						else
							dp[i][j][k][m] += (j - 1) * dp[i-1][j][k - delta][m - 1];
					}						

					// use it as a connector of two components
					if (m == 0)
						dp[i][j][k][m] += j * (j + 1) * dp[i-1][j+1][k - delta][m];
					else if (m == 1)
						dp[i][j][k][m] += j * j * dp[i-1][j+1][k - delta][m];
					else{
						if (i == n)
							dp[i][j][k][m] += dp[i-1][j+1][k - delta][m];
						else
							dp[i][j][k][m] += j * (j - 1) * dp[i-1][j + 1][k - delta][m];
					}
					dp[i][j][k][m] %= mod;
					// if (dp[i][j][k][m])
					// 	cout<<i<<" "<<j<<" "<<k<<" "<<m<<" "<<dp[i][j][k][m]<<endl;
				}
			}
		}
	}
	for (int i=0;i<=L;i++)
		Ans += dp[n][1][i][2];
	if (n == 1)
		Ans = 1;
	cout<<Ans % mod<<'\n';
}

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