Submission #1087519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087519		TAhmed33	Skyscraper (JOI16_skyscraper)	C++98	20 / 100	296 ms	244888 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
const int MOD = 1e9 + 7;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
	if (!b) return 1;
	int u = power(a, b >> 1);
	u = mul(u, u);
	if (b & 1) u = mul(u, a);
	return u;
}
int n, l, a[101];
const int B = 1000;
int dp[102][102][2 * B + 1][3];
int ans (int x, int y, int z, int c) {
	if (y < 1 || c < 0 || c > 2 || abs(z) > B) {
		return 0;
	}
	if (x == n + 1) {
		return y == 1 && z >= 0 && z <= l && c == 0;
	}
	int &ret = dp[x][y][z + B][c];
	if (ret != -1) {
		return ret;
	}
	if (y == 1) {
		ret = 0;
		ret = add(ret, mul(c, ans(x + 1, y, z, c)));
		ret = add(ret, mul(c, ans(x + 1, y, z + a[x], c - 1)));
		ret = add(ret, mul(c, ans(x + 1, y + 1, z - 2 * a[x], c)));
		ret = add(ret, mul(c, ans(x + 1, y + 1, z - a[x], c - 1)));
		return ret;
	}
	ret = 0;
	ret = add(ret, mul(c, ans(x + 1, y + 1, z - 2 * a[x], c)));
	ret = add(ret, mul(c, ans(x + 1, y + 1, z - a[x], c - 1)));
	ret = add(ret, mul(c, ans(x + 1, y, z + a[x], c - 1)));
	ret = add(ret, mul(y - 1, ans(x + 1, y + 1, z - 2 * a[x], c)));
	ret = add(ret, mul(y - 1, ans(x + 1, y - 1, z + 2 * a[x], c)));
	ret = add(ret, mul(2 * y - 2 + c, ans(x + 1, y, z, c)));
	return ret;
}
void solve () {
	memset(dp, -1, sizeof(dp));
	cin >> n >> l;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n == 1) {
		cout << 1 << '\n';
		return;
	}
	sort(a + 1, a + n + 1);
	int sum = ans(2, 1, -a[1], 1);
	sum = mul(sum, 2);
	sum = add(sum, ans(2, 1, -2 * a[1], 2));
	cout << sum << '\n';
}				
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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