QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216829#2430. Gem IslandSwarthmore#AC ✓2600ms1969072kbC++172.1kb2023-10-16 01:47:282023-10-16 01:47:29

Judging History

你现在查看的是最新测评结果

  • [2023-10-16 01:47:29]
  • 评测
  • 测评结果:AC
  • 用时:2600ms
  • 内存:1969072kb
  • [2023-10-16 01:47:28]
  • 提交

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