제출 #1285481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285481		Jawad_Akbar_JJ	Skyscraper (JOI16_skyscraper)	C++20	5 / 100	2 ms	1352 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);

	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)
						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];

					// 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 + j) * 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 - j) * 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