QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#756196#8037. Gambler's RuinSymmetreeWA 1ms10036kbC++171.3kb2024-11-16 19:20:132024-11-16 19:20:14

Judging History

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

  • [2024-11-16 19:20:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10036kb
  • [2024-11-16 19:20:13]
  • 提交

answer

#include<bits/stdc++.h>
const int N = 1e6+5;
using i64 = long long;
std::pair<double, int> p[N];
i64 pre[N], suf[N];
double f[22][N];
int n, mxp[N], t[N];
#define fi first
#define se second
signed main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lf%d", &p[i].fi, &p[i].se);
	std::sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; ++i) {
		pre[i] = pre[i - 1] + p[i].se;
		f[0][i] = 1.0 * pre[i] - 1.0 * pre[i] / (1 - p[i].fi);
	}
	for(int i = 2; i <= n; ++i) t[i] = t[i >> 1] + 1;
	for(int i = n; i; --i) suf[i] = suf[i + 1] + p[i].se;
	for(int k = 1; k < 21; ++k)
		for(int i = 1; i + (1 << k) - 1 <= n; ++i)
			f[k][i] = std::max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]);
	double ans = -1e18;
	for(int i = 1; i <= n; ++i) {
		int pos, l = 1, r = i - 1;
		double bd = 1.0 * suf[i] / p[i].fi;
		ans = std::max(ans, 1.0 * suf[i] - bd);
		if(i == 1) continue;
		while(l < r) {
			int mid = (l + r) >> 1;
			if(1.0 * pre[mid] / (1.0 - p[mid].fi) >= bd) r = mid;
			else l = mid + 1;
		}
		if(1.0 * pre[r] / (1.0 - p[r].fi) >= bd) {
			int k = t[i - r];
			ans = std::max(ans, 1.0 * suf[i] + std::max(f[k][r], f[k][i - (1 << k)]));
			if(r > 1) ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[r - 1] - bd);
		}
		else
			ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[i - 1] - bd);
	}
	printf("%.10lf\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10012kb

input:

2
1 15
0 10

output:

10.0000000000

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 10036kb

input:

3
0.4 100
0.5 100
0.6 100

output:

33.3333333333

result:

ok found '33.3333333', expected '33.3333333', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 7932kb

input:

1
0 1

output:

-1000000000000000000.0000000000

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '-1000000000000000000.0000000', error = '1000000000000000000.0000000'