QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216829 | #2430. Gem Island | Swarthmore# | AC ✓ | 2600ms | 1969072kb | C++17 | 2.1kb | 2023-10-16 01:47:28 | 2023-10-16 01:47:29 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
const char nl = '\n';
ld dp[501][501][501];
void solve() {
ld logs[1001];
FOR(i, 1, 1001) {
logs[i] = log(i);
}
ld logFac[1001];
logFac[0] =0 ;
FOR(i, 1, 1001) {
logFac[i] = logFac[i-1] + logs[i];
}
F0R(i, 501) F0R(j, 501) F0R(k, 501) dp[i][j][k] = -1000;
int N, D, R; cin >> N >> D >> R;
dp[0][D][D] = 0;
ld ans = -1000;
F0R(i, N+1) {
F0Rd(j, D+1) {
F0Rd(k, D+1) {
//cout << i << " " << j << " " << k << ": " << dp[i][j][k] << " " << exp(dp[i][j][k]) << nl;
if (dp[i][j][k] < -999) {
continue;
}
if ((N-i) * k < j) continue;
if (k == 0) {
if (j == 0) {
ld cur = dp[i][j][k];
if (i < R) cur += logs[D];
ans = log(exp(ans) + exp(cur));
}
continue;
}
ld nv = dp[i][j][k];
if (k) {
dp[i][j][k-1] = log(exp(dp[i][j][k-1]) + exp(dp[i][j][k]));
}
for (int nxt = 1; nxt * k <= j && nxt + i <= N; nxt++) {
nv += logs[N-i-nxt+1]; nv -= logs[nxt];
nv += logFac[j-(nxt-1)*k]; nv -= logFac[j-nxt*k];
if (i+nxt == R) {
nv += logs[D-(j-nxt*k)];
}
//cout << i << " " << j << " " << k << " " << nxt << " " << exp(nv) << nl;
dp[i+nxt][j-nxt*k][k-1] = log(exp(dp[i+nxt][j-nxt*k][k-1]) + exp(nv));
}
}
}
}
FOR(i, N, N+D) {
ans -= logs[i];
}
cout << fixed << setprecision(15) << exp(ans) + R << nl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 331ms
memory: 1968948kb
Test #2:
score: 0
Accepted
time: 335ms
memory: 1968736kb
Test #3:
score: 0
Accepted
time: 314ms
memory: 1968828kb
Test #4:
score: 0
Accepted
time: 312ms
memory: 1968980kb
Test #5:
score: 0
Accepted
time: 328ms
memory: 1968828kb
Test #6:
score: 0
Accepted
time: 302ms
memory: 1969008kb
Test #7:
score: 0
Accepted
time: 297ms
memory: 1969016kb
Test #8:
score: 0
Accepted
time: 314ms
memory: 1968916kb
Test #9:
score: 0
Accepted
time: 295ms
memory: 1968996kb
Test #10:
score: 0
Accepted
time: 283ms
memory: 1968960kb
Test #11:
score: 0
Accepted
time: 263ms
memory: 1968956kb
Test #12:
score: 0
Accepted
time: 292ms
memory: 1968956kb
Test #13:
score: 0
Accepted
time: 312ms
memory: 1969020kb
Test #14:
score: 0
Accepted
time: 303ms
memory: 1968976kb
Test #15:
score: 0
Accepted
time: 335ms
memory: 1968956kb
Test #16:
score: 0
Accepted
time: 300ms
memory: 1968956kb
Test #17:
score: 0
Accepted
time: 288ms
memory: 1969004kb
Test #18:
score: 0
Accepted
time: 304ms
memory: 1968900kb
Test #19:
score: 0
Accepted
time: 348ms
memory: 1968972kb
Test #20:
score: 0
Accepted
time: 280ms
memory: 1968972kb
Test #21:
score: 0
Accepted
time: 304ms
memory: 1968884kb
Test #22:
score: 0
Accepted
time: 299ms
memory: 1969016kb
Test #23:
score: 0
Accepted
time: 304ms
memory: 1968916kb
Test #24:
score: 0
Accepted
time: 300ms
memory: 1968896kb
Test #25:
score: 0
Accepted
time: 280ms
memory: 1968824kb
Test #26:
score: 0
Accepted
time: 311ms
memory: 1968884kb
Test #27:
score: 0
Accepted
time: 268ms
memory: 1968888kb
Test #28:
score: 0
Accepted
time: 307ms
memory: 1968912kb
Test #29:
score: 0
Accepted
time: 276ms
memory: 1968956kb
Test #30:
score: 0
Accepted
time: 307ms
memory: 1968968kb
Test #31:
score: 0
Accepted
time: 308ms
memory: 1969072kb
Test #32:
score: 0
Accepted
time: 295ms
memory: 1968824kb
Test #33:
score: 0
Accepted
time: 259ms
memory: 1968900kb
Test #34:
score: 0
Accepted
time: 305ms
memory: 1968896kb
Test #35:
score: 0
Accepted
time: 316ms
memory: 1968732kb
Test #36:
score: 0
Accepted
time: 319ms
memory: 1968896kb
Test #37:
score: 0
Accepted
time: 307ms
memory: 1968896kb
Test #38:
score: 0
Accepted
time: 289ms
memory: 1968968kb
Test #39:
score: 0
Accepted
time: 291ms
memory: 1968824kb
Test #40:
score: 0
Accepted
time: 281ms
memory: 1968900kb
Test #41:
score: 0
Accepted
time: 328ms
memory: 1968952kb
Test #42:
score: 0
Accepted
time: 312ms
memory: 1968980kb
Test #43:
score: 0
Accepted
time: 317ms
memory: 1969016kb
Test #44:
score: 0
Accepted
time: 271ms
memory: 1968968kb
Test #45:
score: 0
Accepted
time: 292ms
memory: 1969020kb
Test #46:
score: 0
Accepted
time: 304ms
memory: 1968828kb
Test #47:
score: 0
Accepted
time: 335ms
memory: 1968980kb
Test #48:
score: 0
Accepted
time: 303ms
memory: 1968908kb
Test #49:
score: 0
Accepted
time: 352ms
memory: 1968952kb
Test #50:
score: 0
Accepted
time: 352ms
memory: 1968956kb
Test #51:
score: 0
Accepted
time: 363ms
memory: 1968888kb
Test #52:
score: 0
Accepted
time: 353ms
memory: 1968888kb
Test #53:
score: 0
Accepted
time: 287ms
memory: 1968960kb
Test #54:
score: 0
Accepted
time: 625ms
memory: 1968892kb
Test #55:
score: 0
Accepted
time: 593ms
memory: 1968980kb
Test #56:
score: 0
Accepted
time: 308ms
memory: 1968980kb
Test #57:
score: 0
Accepted
time: 307ms
memory: 1968952kb
Test #58:
score: 0
Accepted
time: 322ms
memory: 1968972kb
Test #59:
score: 0
Accepted
time: 336ms
memory: 1968784kb
Test #60:
score: 0
Accepted
time: 331ms
memory: 1968948kb
Test #61:
score: 0
Accepted
time: 520ms
memory: 1969068kb
Test #62:
score: 0
Accepted
time: 267ms
memory: 1969004kb
Test #63:
score: 0
Accepted
time: 284ms
memory: 1968732kb
Test #64:
score: 0
Accepted
time: 296ms
memory: 1968892kb
Test #65:
score: 0
Accepted
time: 1645ms
memory: 1968956kb
Test #66:
score: 0
Accepted
time: 748ms
memory: 1969004kb
Test #67:
score: 0
Accepted
time: 288ms
memory: 1968952kb
Test #68:
score: 0
Accepted
time: 298ms
memory: 1968952kb
Test #69:
score: 0
Accepted
time: 319ms
memory: 1968956kb
Test #70:
score: 0
Accepted
time: 1958ms
memory: 1968916kb
Test #71:
score: 0
Accepted
time: 2555ms
memory: 1968952kb
Test #72:
score: 0
Accepted
time: 2600ms
memory: 1969068kb
Test #73:
score: 0
Accepted
time: 283ms
memory: 1968968kb
Test #74:
score: 0
Accepted
time: 311ms
memory: 1968972kb
Test #75:
score: 0
Accepted
time: 327ms
memory: 1968784kb
Test #76:
score: 0
Accepted
time: 331ms
memory: 1968828kb
Test #77:
score: 0
Accepted
time: 364ms
memory: 1968972kb
Test #78:
score: 0
Accepted
time: 375ms
memory: 1968900kb
Test #79:
score: 0
Accepted
time: 351ms
memory: 1968952kb
Test #80:
score: 0
Accepted
time: 1089ms
memory: 1969004kb
Test #81:
score: 0
Accepted
time: 2545ms
memory: 1968884kb
Test #82:
score: 0
Accepted
time: 2545ms
memory: 1968956kb
Test #83:
score: 0
Accepted
time: 2557ms
memory: 1968824kb
Test #84:
score: 0
Accepted
time: 2554ms
memory: 1968952kb