# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
109710 | 2019-05-07T15:58:15 Z | popovicirobert | Skyscraper (JOI16_skyscraper) | C++14 | 3 ms | 640 KB |
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; const int MOD = (int) 1e9 + 7; inline void mod(int &x) { if(x >= MOD) x -= MOD; } inline void add(int &x, int y) { x += y; mod(x); } const int MAXN = 100; const int MAXL = 1000; int dp[2][MAXN + 1][MAXN * (MAXL + 5)][4]; int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, l, j; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> l; vector <int> arr(n + 1); for(i = 1; i <= n; i++) { cin >> arr[i]; } sort(arr.begin(), arr.end()); int sum = 0; dp[0][0][MAXN * MAXL][0] = 1; for(i = 0; i < n; i++) { sum += arr[i]; for(j = 0; j <= i; j++) { int lim = min(sum, l); for(int cst = -sum; cst <= lim; cst++) { for(int p = 0; p <= 3; p++) { dp[1 - i & 1][j][cst + MAXL * MAXN][p] = 0; } } } for(j = 0; j <= i; j++) { int lim = min(sum, l); for(int cst = -2 * sum + MAXN * MAXL; cst <= lim + MAXN * MAXL; cst++) { for(int p = 0; p <= 3; p++) { int cur = dp[i & 1][j][cst][p]; if(cur == 0) { continue; } if(cst - 2 * arr[i + 1] >= 0) { add(dp[1 - i & 1][j + 1][cst - 2 * arr[i + 1]][p], cur); } if(cst - arr[i + 1] < 0) { continue; } for(int bit = 0; bit <= 1; bit++) { if((p & (1 << bit)) == 0) { add(dp[1 - i & 1][j + 1][cst - arr[i + 1]][p ^ (1 << bit)], cur); } } } for(int p = 0; p <= 3; p++) { int cur = dp[i & 1][j][cst][p]; if(cur == 0) { continue; } int num = __builtin_popcount(p); if(2 * j > num) { add(dp[1 - i & 1][j][cst][p], (1LL * cur * (2 * j - num)) % MOD); } if(cst + arr[i + 1] > MAXN * MAXL + l) { continue; } for(int bit = 0; bit <= 1; bit++) { if((p & (1 << bit)) == 0) { if(i < n - 1) { if(j > num) { add(dp[1 - i & 1][j][cst + arr[i + 1]][p ^ (1 << bit)], (1LL * cur * (j - num)) % MOD); } } else { add(dp[1 - i & 1][j][cst + arr[i + 1]][p ^ (1 << bit)], (1LL * cur * j) % MOD); } } } } if(j <= 1) { continue; } for(int p = 0; p <= 3; p++) { int cur = dp[i & 1][j][cst][p]; if(cur == 0) { continue; } int a = ((p & 2) > 0), b = (p & 1); if(i < n - 1) { int coef = a * (j - a - b) + (j - a - b) * b + (j - a - b) * (j - a - b - 1); if(cst + 2 * arr[i + 1] <= MAXN * MAXL + l) { add(dp[1 - i & 1][j - 1][cst + 2 * arr[i + 1]][p], (1LL * cur * coef) % MOD); } } else { int coef = a * (j - a - b) + (j - a - b) * b + (j - a - b) * (j - a - b - 1) + a * b; if(cst + 2 * arr[i + 1] <= MAXN * MAXL + l) { add(dp[1 - i & 1][j - 1][cst + 2 * arr[i + 1]][p], (1LL * cur * coef) % MOD); } } } } } } int ans = 0; for(i = MAXN * MAXL; i <= l + MAXN * MAXL; i++) { ans += dp[n & 1][1][i][3]; mod(ans); } cout << ans; //cin.close(); //cout.close(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 640 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |