QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380923 | #2430. Gem Island | ckiseki# | AC ✓ | 2155ms | 1984876kb | C++20 | 3.1kb | 2024-04-07 15:03:59 | 2024-04-07 15:03:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
using llf = long double;
const int maxn = 505;
llf g[maxn][maxn][maxn];
llf fac[maxn * 2];
llf pw[maxn * 2];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, d, r;
cin >> n >> d >> r;
fac[0] = 1;
for (int i = 1; i < maxn * 2; i++)
fac[i] = fac[i - 1] * i;
debug((long double)fac[maxn - 1]);
pw[0] = 1;
pw[1] = 1;
{
llf x = fac[n];
x = powl(x, 1.0 / llf(n));
pw[1] *= x;
}
{
llf x = fac[n - 1];
x = powl(x, 1.0 / llf(n));
pw[1] *= x;
}
{
llf x = fac[d];
x = powl(x, 1.0 / llf(n));
pw[1] *= x;
}
{
llf x = fac[n + d - 1];
x = powl(x, 1.0 / llf(n));
pw[1] /= x;
}
debug(pw[1]);
for (int i = 1; i <= n; i++)
{
//pw[i] = //powl(fac[n-1] * fac[d] / fac[n+d-1] * fac[n], i / llf(n));
pw[i] = pw[i - 1] * pw[1];
}
orange(pw, pw + 500);
for (int i = 0; i <= n; i++) {
g[i][0][0] = pw[i] / fac[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= d; j++) {
for (int k = 0; k <= d; k++) {
for (int t = 0; t <= i && j * t <= k; t++) {
g[i][j][k] += g[i-t][j-1][k - j*t] / fac[t] * pw[t];
}
}
}
}
llf sum = 0;
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= d; j++) {
for (int k = 0; k <= d - i * j; k++) {
sum += min(i, r) * g[i][d - j][k] * g[n-i][j-1][d - i * j - k];
}
// orange(g[i][j], g[i][j] + 10);
}
}
debug((long double)sum);
// sum *= fac[n-1];
// sum *= fac[d];
// sum /= fac[n+d-1];
sum += r;
cout << fixed << setprecision(20);
cout << (long double)sum << '\n';
return 0;
}
/*
3 3 2
(fac[maxn - 1]) = (7.77944e+1144)
[ g[i][j], g[i][j] + 10 ] = [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 0.5, 0, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1.5, 1, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1.5, 2, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 0.5, 0.166667, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1.5, 1.16667, 0, 0, 0, 0, 0, 0 ]
[ g[i][j], g[i][j] + 10 ] = [ 1, 1, 1.5, 2.16667, 0, 0, 0, 0, 0, 0 ]
(sum) = (8)
6.80000000000000000017
*/
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 8096kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 10144kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 12148kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 5780kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 6064kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 6084kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 6960kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 11376kb
Test #9:
score: 0
Accepted
time: 3ms
memory: 11912kb
Test #10:
score: 0
Accepted
time: 4ms
memory: 11792kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 8140kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 8104kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 8096kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 7832kb
Test #15:
score: 0
Accepted
time: 1ms
memory: 8128kb
Test #16:
score: 0
Accepted
time: 1ms
memory: 8196kb
Test #17:
score: 0
Accepted
time: 2ms
memory: 8680kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 8744kb
Test #19:
score: 0
Accepted
time: 3ms
memory: 13964kb
Test #20:
score: 0
Accepted
time: 5ms
memory: 15908kb
Test #21:
score: 0
Accepted
time: 7ms
memory: 15644kb
Test #22:
score: 0
Accepted
time: 0ms
memory: 10148kb
Test #23:
score: 0
Accepted
time: 2ms
memory: 10188kb
Test #24:
score: 0
Accepted
time: 1ms
memory: 10128kb
Test #25:
score: 0
Accepted
time: 1ms
memory: 5888kb
Test #26:
score: 0
Accepted
time: 2ms
memory: 7192kb
Test #27:
score: 0
Accepted
time: 2ms
memory: 8304kb
Test #28:
score: 0
Accepted
time: 0ms
memory: 8844kb
Test #29:
score: 0
Accepted
time: 1ms
memory: 5900kb
Test #30:
score: 0
Accepted
time: 1ms
memory: 6132kb
Test #31:
score: 0
Accepted
time: 1ms
memory: 6060kb
Test #32:
score: 0
Accepted
time: 0ms
memory: 6148kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 6148kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 10176kb
Test #35:
score: 0
Accepted
time: 2ms
memory: 10676kb
Test #36:
score: 0
Accepted
time: 2ms
memory: 7152kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 7052kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 8264kb
Test #39:
score: 0
Accepted
time: 1ms
memory: 6028kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 6556kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 7456kb
Test #42:
score: 0
Accepted
time: 0ms
memory: 7620kb
Test #43:
score: 0
Accepted
time: 13ms
memory: 27784kb
Test #44:
score: 0
Accepted
time: 1ms
memory: 8172kb
Test #45:
score: 0
Accepted
time: 0ms
memory: 12352kb
Test #46:
score: 0
Accepted
time: 1ms
memory: 6844kb
Test #47:
score: 0
Accepted
time: 0ms
memory: 8456kb
Test #48:
score: 0
Accepted
time: 3ms
memory: 8504kb
Test #49:
score: 0
Accepted
time: 23ms
memory: 47400kb
Test #50:
score: 0
Accepted
time: 23ms
memory: 47672kb
Test #51:
score: 0
Accepted
time: 36ms
memory: 59032kb
Test #52:
score: 0
Accepted
time: 32ms
memory: 71648kb
Test #53:
score: 0
Accepted
time: 3ms
memory: 35260kb
Test #54:
score: 0
Accepted
time: 155ms
memory: 205072kb
Test #55:
score: 0
Accepted
time: 173ms
memory: 205124kb
Test #56:
score: 0
Accepted
time: 8ms
memory: 41100kb
Test #57:
score: 0
Accepted
time: 0ms
memory: 21132kb
Test #58:
score: 0
Accepted
time: 4ms
memory: 21000kb
Test #59:
score: 0
Accepted
time: 20ms
memory: 70480kb
Test #60:
score: 0
Accepted
time: 16ms
memory: 70752kb
Test #61:
score: 0
Accepted
time: 119ms
memory: 283908kb
Test #62:
score: 0
Accepted
time: 0ms
memory: 29428kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 26296kb
Test #64:
score: 0
Accepted
time: 16ms
memory: 79392kb
Test #65:
score: 0
Accepted
time: 998ms
memory: 996576kb
Test #66:
score: 0
Accepted
time: 403ms
memory: 667696kb
Test #67:
score: 0
Accepted
time: 12ms
memory: 97136kb
Test #68:
score: 0
Accepted
time: 4ms
memory: 59200kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 21824kb
Test #70:
score: 0
Accepted
time: 1653ms
memory: 1765088kb
Test #71:
score: 0
Accepted
time: 2087ms
memory: 1953124kb
Test #72:
score: 0
Accepted
time: 2097ms
memory: 1976968kb
Test #73:
score: 0
Accepted
time: 0ms
memory: 24072kb
Test #74:
score: 0
Accepted
time: 0ms
memory: 15912kb
Test #75:
score: 0
Accepted
time: 3ms
memory: 36796kb
Test #76:
score: 0
Accepted
time: 88ms
memory: 296644kb
Test #77:
score: 0
Accepted
time: 135ms
memory: 384320kb
Test #78:
score: 0
Accepted
time: 155ms
memory: 384280kb
Test #79:
score: 0
Accepted
time: 119ms
memory: 382604kb
Test #80:
score: 0
Accepted
time: 934ms
memory: 1331348kb
Test #81:
score: 0
Accepted
time: 2155ms
memory: 1984804kb
Test #82:
score: 0
Accepted
time: 2095ms
memory: 1984548kb
Test #83:
score: 0
Accepted
time: 2051ms
memory: 1984660kb
Test #84:
score: 0
Accepted
time: 2114ms
memory: 1984876kb