Submission #1087522

#TimeUsernameProblemLanguageResultExecution timeMemory
1087522TAhmed33Skyscraper (JOI16_skyscraper)C++98
20 / 100
2065 ms151164 KiB
#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 = 2000; map <int, int> dp[102][102][3]; int ans (int x, int y, int z, int c) { if (y < 1 || c < 0 || c > 2) { return 0; } if (x == n + 1) { return y == 1 && z >= 0 && z <= l && c == 0; } if (dp[x][y][c].count(z)) { return dp[x][y][c][z]; } int ret = 0; if (y == 1) { 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))); } else { 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 dp[x][y][c][z] = ret; } void solve () { 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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...