Submission #43720

#	Time	Username	Problem	Language	Result	Execution time	Memory
43720		RezwanArefin01	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	297 ms	240776 KiB

skyscraper

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

typedef long long ll;
typedef pair<int, int> ii; 

const int mod = 1e9 + 7;
int a[101], n, L;
ll dp[101][101][3][1001]; 

ll f(int i, int g, int end, int sum) {
	sum += (a[i] - a[i - 1]) * (2 * g + end); 
	if(g < 0 || end > 2 || sum > L) return 0; 
	if(i == n) return g == 0 && end;
	ll &ret = dp[i][g][end][sum];
	if(~ret) return ret; 

	ret = (g + 1) * f(i + 1, g + 1, end, sum);
	ret += (2 * g + end) * f(i + 1, g, end, sum); 
	ret += (g + end - 1) * f(i + 1, g - 1, end, sum); 
	ret += (2 - end) * f(i + 1, g, end + 1, sum);
	ret += (2 - end) * f(i + 1, g - 1, end + 1, sum); 
	ret %= mod;
	return ret;
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	scanf("%d %d", &n, &L); 
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]); 
	} sort(a + 1, a + n + 1); 
	memset(dp, -1, sizeof dp);
	printf("%lld\n", n == 1 ? 1 : f(1, 0, 0, 0));
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:30:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &L); 
                        ^
skyscraper.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]); 
                     ^

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