QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71792 | #2430. Gem Island | He_Ren | AC ✓ | 334ms | 23040kb | C++14 | 1.2kb | 2023-01-12 01:15:14 | 2023-01-12 01:15:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
const int MAXN = 500 + 5;
const int MAXF = MAXN * 2;
ldb C[MAXF][MAXF];
int main(void) {
int n, d, r;
scanf("%d%d%d", &n, &d, &r);
for (int i = 0; i <= n + d; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
ldb ans = 0;
for (int i = 1; i <= d; ++i) {
static ldb f[MAXN][MAXN];
f[0][0] = 1;
for (int j = 1; j <= n; ++j) {
ldb cur = 0;
for (int k = 0; k <= d; ++k) {
cur += f[j - 1][k];
if (k - i >= 0)
cur -= f[j - 1][k - i];
f[j][k] = cur;
}
}
for (int j = 1; j <= n && i * j <= d; ++j)
for (int k = 0; i * j + k <= d; ++k)
ans += f[n - j][d - i * j - k] * C[k + j - 1][j - 1] * C[n][j] * min(r, j);
}
for (int i = 1; i <= d; ++i)
ans = ans * i / (n + i - 1);
ans += r;
printf("%.20lf", (double)ans);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 2ms
memory: 5692kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 5712kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 5920kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 5644kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 5652kb
Test #6:
score: 0
Accepted
time: 3ms
memory: 7820kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 6352kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 12080kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 12064kb
Test #10:
score: 0
Accepted
time: 5ms
memory: 11848kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 5704kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 5868kb
Test #13:
score: 0
Accepted
time: 1ms
memory: 7864kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 5648kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 5668kb
Test #16:
score: 0
Accepted
time: 2ms
memory: 5824kb
Test #17:
score: 0
Accepted
time: 0ms
memory: 8156kb
Test #18:
score: 0
Accepted
time: 1ms
memory: 6164kb
Test #19:
score: 0
Accepted
time: 2ms
memory: 11784kb
Test #20:
score: 0
Accepted
time: 2ms
memory: 14376kb
Test #21:
score: 0
Accepted
time: 2ms
memory: 11916kb
Test #22:
score: 0
Accepted
time: 2ms
memory: 5792kb
Test #23:
score: 0
Accepted
time: 1ms
memory: 5792kb
Test #24:
score: 0
Accepted
time: 0ms
memory: 5736kb
Test #25:
score: 0
Accepted
time: 2ms
memory: 5820kb
Test #26:
score: 0
Accepted
time: 2ms
memory: 6032kb
Test #27:
score: 0
Accepted
time: 2ms
memory: 8044kb
Test #28:
score: 0
Accepted
time: 0ms
memory: 8000kb
Test #29:
score: 0
Accepted
time: 3ms
memory: 5688kb
Test #30:
score: 0
Accepted
time: 2ms
memory: 5796kb
Test #31:
score: 0
Accepted
time: 2ms
memory: 5788kb
Test #32:
score: 0
Accepted
time: 2ms
memory: 5668kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 5840kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 5724kb
Test #35:
score: 0
Accepted
time: 3ms
memory: 6044kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 6128kb
Test #37:
score: 0
Accepted
time: 2ms
memory: 5940kb
Test #38:
score: 0
Accepted
time: 3ms
memory: 8228kb
Test #39:
score: 0
Accepted
time: 2ms
memory: 5896kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 5740kb
Test #41:
score: 0
Accepted
time: 3ms
memory: 6120kb
Test #42:
score: 0
Accepted
time: 3ms
memory: 6080kb
Test #43:
score: 0
Accepted
time: 4ms
memory: 12036kb
Test #44:
score: 0
Accepted
time: 3ms
memory: 5768kb
Test #45:
score: 0
Accepted
time: 2ms
memory: 5904kb
Test #46:
score: 0
Accepted
time: 2ms
memory: 5796kb
Test #47:
score: 0
Accepted
time: 3ms
memory: 7772kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 5952kb
Test #49:
score: 0
Accepted
time: 8ms
memory: 12048kb
Test #50:
score: 0
Accepted
time: 11ms
memory: 12372kb
Test #51:
score: 0
Accepted
time: 9ms
memory: 12180kb
Test #52:
score: 0
Accepted
time: 4ms
memory: 10440kb
Test #53:
score: 0
Accepted
time: 4ms
memory: 7856kb
Test #54:
score: 0
Accepted
time: 33ms
memory: 12408kb
Test #55:
score: 0
Accepted
time: 34ms
memory: 12408kb
Test #56:
score: 0
Accepted
time: 2ms
memory: 7996kb
Test #57:
score: 0
Accepted
time: 1ms
memory: 7788kb
Test #58:
score: 0
Accepted
time: 3ms
memory: 6344kb
Test #59:
score: 0
Accepted
time: 2ms
memory: 8292kb
Test #60:
score: 0
Accepted
time: 0ms
memory: 8384kb
Test #61:
score: 0
Accepted
time: 29ms
memory: 12020kb
Test #62:
score: 0
Accepted
time: 4ms
memory: 12204kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 12028kb
Test #64:
score: 0
Accepted
time: 4ms
memory: 12756kb
Test #65:
score: 0
Accepted
time: 161ms
memory: 16752kb
Test #66:
score: 0
Accepted
time: 67ms
memory: 14728kb
Test #67:
score: 0
Accepted
time: 2ms
memory: 13644kb
Test #68:
score: 0
Accepted
time: 2ms
memory: 13160kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 13864kb
Test #70:
score: 0
Accepted
time: 259ms
memory: 21720kb
Test #71:
score: 0
Accepted
time: 334ms
memory: 21772kb
Test #72:
score: 0
Accepted
time: 328ms
memory: 22540kb
Test #73:
score: 0
Accepted
time: 2ms
memory: 13896kb
Test #74:
score: 0
Accepted
time: 2ms
memory: 14380kb
Test #75:
score: 0
Accepted
time: 2ms
memory: 14100kb
Test #76:
score: 0
Accepted
time: 12ms
memory: 15060kb
Test #77:
score: 0
Accepted
time: 19ms
memory: 15916kb
Test #78:
score: 0
Accepted
time: 27ms
memory: 16080kb
Test #79:
score: 0
Accepted
time: 23ms
memory: 15456kb
Test #80:
score: 0
Accepted
time: 145ms
memory: 19440kb
Test #81:
score: 0
Accepted
time: 317ms
memory: 22684kb
Test #82:
score: 0
Accepted
time: 317ms
memory: 23040kb
Test #83:
score: 0
Accepted
time: 317ms
memory: 22824kb
Test #84:
score: 0
Accepted
time: 313ms
memory: 21948kb