Submission #208665

#	Time	Username	Problem	Language	Result	Execution time	Memory
208665		bensonlzl	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	249 ms	260872 KiB

skyscraper

#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;
	if (N == 1){
		cout << 1 << '\n';
		return 0;
	}
	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';
}

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