| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 109712 | 2019-05-07T16:05:23 Z | popovicirobert | Skyscraper (JOI16_skyscraper) | C++14 | 7 ms | 1024 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][2 * 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][2 * MAXN * MAXL][0] = 1;
for(i = 0; i < n; i++) {
sum += arr[i];
for(j = 0; j <= i; j++) {
int lim = min(2 * sum, l);
for(int cst = -2 * sum; cst <= lim; cst++) {
for(int p = 0; p <= 3; p++) {
dp[1 - i & 1][j][cst + 2 * MAXL * MAXN][p] = 0;
}
}
}
for(j = 0; j <= i; j++) {
int lim = min(2 * sum, l);
for(int cst = -2 * sum + 2 * MAXN * MAXL; cst <= lim + 2 * 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) {
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);
add(dp[1 - i & 1][j][cst][p], (1LL * cur * max(0, 2 * j - num)) % MOD);
if(cst + arr[i + 1] <= 2 * MAXN * MAXL + l) {
for(int bit = 0; bit <= 1; bit++) {
if((p & (1 << bit)) == 0) {
if(i < n - 1) {
add(dp[1 - i & 1][j][cst + arr[i + 1]][p ^ (1 << bit)], (1LL * cur * max(0, 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(cst + 2 * arr[i + 1] <= 2 * MAXN * MAXL + l) {
if(i < n - 1) {
int coef = max(0, a * (j - a - b)) + max(0, (j - a - b) * b) + max(0, (j - a - b) * (j - a - b - 1));
add(dp[1 - i & 1][j - 1][cst + 2 * arr[i + 1]][p], (1LL * cur * coef) % MOD);
}
else {
int coef = max(0, a * (j - a - b)) + max(0, (j - a - b) * b) + max(0, (j - a - b) * (j - a - b - 1)) + a * b;
add(dp[1 - i & 1][j - 1][cst + 2 * arr[i + 1]][p], (1LL * cur * coef) % MOD);
}
}
}
}
}
}
int ans = 0;
for(i = 2 * MAXN * MAXL; i <= l + 2 * 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 | 2 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 640 KB | Output is correct |
| 2 | Correct | 7 ms | 1024 KB | Output is correct |
| 3 | Correct | 3 ms | 640 KB | Output is correct |
| 4 | Correct | 7 ms | 1024 KB | Output is correct |
| 5 | Correct | 6 ms | 1024 KB | Output is correct |
| 6 | Correct | 4 ms | 896 KB | Output is correct |
| 7 | Correct | 4 ms | 768 KB | Output is correct |
| 8 | Correct | 3 ms | 768 KB | Output is correct |
| 9 | Correct | 5 ms | 768 KB | Output is correct |
| 10 | Correct | 5 ms | 1024 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |