Submission #208661

#TimeUsernameProblemLanguageResultExecution timeMemory
208661bensonlzlSkyscraper (JOI16_skyscraper)C++14
15 / 100
155 ms260720 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[105][105][1005][3];

ll N, L, A[105], D[105];

const ll mod = 1000000007;

ll calc(int n, int c, int l, int edge){
	if (l < 0) return 0;
	if (n == N) return ((c >= 1) && (c <= 2) && (c == edge));
	if (dp[n][c][l][edge] != -1) return dp[n][c][l][edge];
	ll ans = 0;
	if (edge < 2){
		// Add to one end of the array	
		ans += calc(n+1,c+1,l - (2 * (c+1) - edge - 1) * D[n],edge+1) * (2-edge);

		
		if (2*c - edge - 1 > 0) ans += calc(n+1,c,l - (2*c - edge - 1) * D[n],edge+1) * (2-edge);
	}
	// Add new segment
	if (c + 1 - edge > 0) ans += calc(n+1,c+1,l - (2*(c+1) - edge) * D[n], edge) * (c + 1 - edge);
	
	// Merge 2 existing segments
	if (c > 0) ans += calc(n+1,c-1,l - (2*(c-1) - edge) * D[n], edge) * (c-1);
	
	// Add to an existing segment
	if (2*c > edge) ans += calc(n+1,c,l - (2*c - edge) * D[n], edge) * (2 * c - edge);
	ans %= mod;
	return dp[n][c][l][edge] = ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	memset(dp,-1,sizeof(dp));
	cin >> N >> L;
	for (int i = 1; i <= N; ++i){
		cin >> A[i];
	}
	sort(A+1,A+N+1);
	for (int i = 1; i <= N; ++i){
		D[i] = A[i+1] - A[i];
	}
	cout << calc(1,0,L,0) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...