QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381063 | #2430. Gem Island | ckiseki | AC ✓ | 2072ms | 1984648kb | C++20 | 2.7kb | 2024-04-07 16:10:06 | 2024-04-07 16:10:07 |
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]);
for (int i = 1; i <= n; i++)
{
pw[i] = powl(fac[n-1] * fac[d] / fac[n+d-1] * fac[n], i / llf(n));
}
orange(pw, pw + 500);
for (int i = 0; i <= n; i++) {
g[i][0][0] = 1 / 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] * 1;
}
}
}
}
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 *= pw[n];
sum *= fac[n-1];
sum *= fac[d];
sum /= fac[n+d-1];
sum *= fac[n];
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: 6020kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 4052kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 4268kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 4016kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 4028kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 4028kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 5140kb
Test #8:
score: 0
Accepted
time: 3ms
memory: 11068kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 11872kb
Test #10:
score: 0
Accepted
time: 5ms
memory: 11844kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 4004kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 4056kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #14:
score: 0
Accepted
time: 0ms
memory: 4028kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 4132kb
Test #16:
score: 0
Accepted
time: 1ms
memory: 4132kb
Test #17:
score: 0
Accepted
time: 2ms
memory: 5728kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 5708kb
Test #19:
score: 0
Accepted
time: 6ms
memory: 10412kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 15852kb
Test #21:
score: 0
Accepted
time: 5ms
memory: 15712kb
Test #22:
score: 0
Accepted
time: 1ms
memory: 6052kb
Test #23:
score: 0
Accepted
time: 0ms
memory: 4016kb
Test #24:
score: 0
Accepted
time: 1ms
memory: 4000kb
Test #25:
score: 0
Accepted
time: 1ms
memory: 4156kb
Test #26:
score: 0
Accepted
time: 2ms
memory: 5628kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 6216kb
Test #28:
score: 0
Accepted
time: 0ms
memory: 7300kb
Test #29:
score: 0
Accepted
time: 0ms
memory: 3988kb
Test #30:
score: 0
Accepted
time: 1ms
memory: 4024kb
Test #31:
score: 0
Accepted
time: 0ms
memory: 4040kb
Test #32:
score: 0
Accepted
time: 1ms
memory: 3848kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 4100kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3848kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 5356kb
Test #36:
score: 0
Accepted
time: 2ms
memory: 5084kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 5220kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 6820kb
Test #39:
score: 0
Accepted
time: 1ms
memory: 4200kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 4588kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 5684kb
Test #42:
score: 0
Accepted
time: 0ms
memory: 5928kb
Test #43:
score: 0
Accepted
time: 13ms
memory: 27752kb
Test #44:
score: 0
Accepted
time: 1ms
memory: 4248kb
Test #45:
score: 0
Accepted
time: 1ms
memory: 4248kb
Test #46:
score: 0
Accepted
time: 0ms
memory: 4876kb
Test #47:
score: 0
Accepted
time: 2ms
memory: 6728kb
Test #48:
score: 0
Accepted
time: 2ms
memory: 6664kb
Test #49:
score: 0
Accepted
time: 23ms
memory: 47468kb
Test #50:
score: 0
Accepted
time: 38ms
memory: 47468kb
Test #51:
score: 0
Accepted
time: 35ms
memory: 58676kb
Test #52:
score: 0
Accepted
time: 19ms
memory: 61700kb
Test #53:
score: 0
Accepted
time: 9ms
memory: 25016kb
Test #54:
score: 0
Accepted
time: 145ms
memory: 204784kb
Test #55:
score: 0
Accepted
time: 144ms
memory: 204788kb
Test #56:
score: 0
Accepted
time: 0ms
memory: 26600kb
Test #57:
score: 0
Accepted
time: 1ms
memory: 4796kb
Test #58:
score: 0
Accepted
time: 0ms
memory: 4692kb
Test #59:
score: 0
Accepted
time: 15ms
memory: 58304kb
Test #60:
score: 0
Accepted
time: 12ms
memory: 58456kb
Test #61:
score: 0
Accepted
time: 101ms
memory: 279964kb
Test #62:
score: 0
Accepted
time: 0ms
memory: 13424kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 10068kb
Test #64:
score: 0
Accepted
time: 7ms
memory: 64948kb
Test #65:
score: 0
Accepted
time: 912ms
memory: 996284kb
Test #66:
score: 0
Accepted
time: 366ms
memory: 662128kb
Test #67:
score: 0
Accepted
time: 7ms
memory: 82016kb
Test #68:
score: 0
Accepted
time: 11ms
memory: 45460kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 9572kb
Test #70:
score: 0
Accepted
time: 1503ms
memory: 1761652kb
Test #71:
score: 0
Accepted
time: 1816ms
memory: 1952980kb
Test #72:
score: 0
Accepted
time: 1905ms
memory: 1976656kb
Test #73:
score: 0
Accepted
time: 0ms
memory: 7968kb
Test #74:
score: 0
Accepted
time: 0ms
memory: 7748kb
Test #75:
score: 0
Accepted
time: 3ms
memory: 26768kb
Test #76:
score: 0
Accepted
time: 67ms
memory: 284684kb
Test #77:
score: 0
Accepted
time: 140ms
memory: 370732kb
Test #78:
score: 0
Accepted
time: 128ms
memory: 370896kb
Test #79:
score: 0
Accepted
time: 107ms
memory: 371912kb
Test #80:
score: 0
Accepted
time: 810ms
memory: 1324432kb
Test #81:
score: 0
Accepted
time: 1957ms
memory: 1984648kb
Test #82:
score: 0
Accepted
time: 1905ms
memory: 1984432kb
Test #83:
score: 0
Accepted
time: 2034ms
memory: 1984620kb
Test #84:
score: 0
Accepted
time: 2072ms
memory: 1984648kb