Submission #362398

#	Time	Username	Problem	Language	Result	Execution time	Memory
362398		Blerargh	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	438 ms	236896 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MAXN = 105;
const ll COST = 1005;
const ll MOD = 1e9+7;

ll dp[MAXN][MAXN][COST][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll N, L;
	cin >> N >> L;
	
	if (N == 1){
		cout << "1";
		return 0;
	}
	
	dp[0][0][0][0] = 1;
	
	vector<ll> heights;
	for (int i=0; i<N; i++){
		ll x;
		cin >> x;
		heights.push_back(x);
	}
	heights.push_back(0);
	sort(heights.begin(), heights.end());
	
	for (int i=1; i<=N; i++){
		ll C = heights[i] - heights[i-1];
		if (i==1) C = 0;
		for (int j=1; j<=N; j++){
			for (int k=0; k<=L; k++){
				for (int l=0; l<3; l++){
					//adding a component without closing any end
					if (k - (2*j-2-l)*C >= 0) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-2-l)*C][l];
					
					//adding a component and closing one end
					if (k - (2*j-1-l)*C >= 0 && l){
						if (l==1) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-1-l)*C][l-1] * 2;
						if (l==2) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-1-l)*C][l-1];
					}
					
					//adding to a component without closing any end
					if (k - (2*j-l)*C >= 0) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l)*C][l] * (2*j - l);
					
					//adding to a component and closing one end
					if (i==N && j==1 && k-C>=0 && l==2) dp[i][j][k][l] += dp[i-1][j][k - C][l-1];
					else if (k - (2*j-l+1)*C >= 0){
						if (l == 1) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l+1)*C][l-1] * (2 * j);
						if (l == 2) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l+1)*C][l-1] * (j - 1);
					}
					
					//merging two components
					if (i==N && j==1 && k-2*C>=0 && l==2) dp[i][j][k][l] += dp[i-1][j+1][k - 2*C][l];
					else if (k - (2*j+2-l)*C >= 0) {
						if (l==0) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * (j+1) * j;
						if (l==1) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * j * j;
						if (l==2) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * (j-1) * j; 
					}
					
					dp[i][j][k][l] %= MOD;
				}
			}
		}
	}
	
	ll ans=0;
	for (int cost=0; cost<=L; cost++){
		ans += dp[N][1][cost][2];
		ans %= MOD;
	}
	cout << ans;
}

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