QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110507 | #5552. Skyscraper | Scintilla | 15 | 2ms | 4044kb | C++14 | 2.1kb | 2023-06-02 17:34:42 | 2023-06-02 17:35:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int P = 1e9 + 7;
const int N = 1e2 + 10;
const int M = 1e3 + 10;
const int W = 1e3;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
void add(int &a, int b) { (a += b) >= P ? a -= P : 1; }
void sub(int &a, int b) { (a -= b) < 0 ? a += P : 1; }
int sgn(int x) { return x & 1 ? P - 1 : 1; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }
int n, m, a[N], f[N][N][M][2][2], ans;
int main() {
n = read(), m = read();
rep(i, 1, n) a[i] = read();
sort(a + 1, a + n + 1);
f[0][0][0][0][0] = 1;
rep(i, 0, n - 1) rep(j, 0, min(i, n - i + 1)) {
rep(s, 0, m) rep(p, 0, 1) rep(q, 0, 1) {
int cur = f[i][j][s][p][q], ns = s + (2 * j - p - q) * (a[i + 1] - a[i]);
if (!cur || ns > m) continue;
if (!p) add(f[i + 1][j + 1][ns][1][q], cur);
if (!q) add(f[i + 1][j + 1][ns][p][1], cur);
add(f[i + 1][j + 1][ns][p][q], cur);
if (!p) add(f[i + 1][j][ns][1][q], mul(cur, j - (i + 1 < n && q)));
add(f[i + 1][j][ns][p][q], mul(cur, j - (i + 1 < n && q)));
if (!q) add(f[i + 1][j][ns][p][1], mul(cur, j - (i + 1 < n && p)));
add(f[i + 1][j][ns][p][q], mul(cur, j - (i + 1 < n && p)));
if (j > 1) {
int coef = (j - q) * (j - p) - (j - p - q) - (p && q && i + 1 < n);
add(f[i + 1][j - 1][ns][p][q], mul(cur, coef));
}
}
}
rep(s, 0, m) add(ans, f[n][1][s][1][1]);
printf("%d\n", ans);
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3556kb
input:
1 1 8
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 2ms
memory: 3744kb
input:
12 63 8 2 6 3 11 9 1 12 4 5 10 7
output:
472261248
result:
ok single line: '472261248'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
14 96 17 36 98 27 13 68 11 34 80 50 22 73 94 37
output:
44
result:
ok single line: '44'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3984kb
input:
14 45 6 9 12 15 18 2 14 5 11 17 4 3 7 10
output:
183056086
result:
ok single line: '183056086'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
14 97 25 2 54 78 9 29 34 99 82 36 14 66 15 64
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3908kb
input:
14 98 26 70 16 95 30 2 18 96 6 5 52 99 89 24
output:
2
result:
ok single line: '2'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
14 92 33 3 17 38 39 45 2 48 22 29 9 28 5 10
output:
1235526
result:
ok single line: '1235526'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
14 29 12 6 16 9 23 20 3 1 8 25 29 26 19 24
output:
2
result:
ok single line: '2'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
14 43 17 11 7 8 5 2 10 16 12 9 15 3 14 18
output:
110733412
result:
ok single line: '110733412'
Test #19:
score: 0
Accepted
time: 2ms
memory: 4044kb
input:
14 72 7 13 19 16 20 15 4 10 1 6 14 11 5 8
output:
347124497
result:
ok single line: '347124497'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
14 83 18 73 40 48 86 97 24 21 45 69 36 16 26 35
output:
6
result:
ok single line: '6'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%