QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661835#8037. Gambler's RuininoaderWA 562ms36936kbC++141.1kb2024-10-20 18:26:112024-10-20 18:26:12

Judging History

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

  • [2024-10-20 18:26:12]
  • 评测
  • 测评结果:WA
  • 用时:562ms
  • 内存:36936kb
  • [2024-10-20 18:26:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define endl '\n'
inline int read(){
	int x=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')k=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*k;
}
const int N=1e6+5;
const long double eps=1e-13;
long double p[N];
int n;
struct node{
	long double p;
	int c;
}a[N];
bool cmp(node x,node y){
	return x.p>y.p;
}
void sol(){
	n=read();
	for(int i=1;i<=n;++i){
		cin>>a[i].p;
		a[i].c=read();
	}
	sort(a+1,a+1+n,cmp);
	int sx=0;
	long double ans=0;
	int r=n;
	int sy=0;
	long double y=1;
	for(int i=1;i<=n;++i){
		while(i>r){
			sy-=a[r+1].c;
			y=1/(1-a[r+1].p);
			++r;
		}
		sx+=a[i].c;
		if(a[i].p==a[i+1].p)continue;
		long double x=1/a[i].p;
		while(r>i){
			int rr=r;
			int ssy=sy+a[r].c;
			while(a[rr-1].p==a[rr].p)ssy+=a[--rr].c;
			long double yy=1/(1-a[rr].p);
			if(ssy-max(sx*x,ssy*yy)>sy-max(sx*x,sy*y))sy=ssy,y=yy,r=rr-1;
			else break;
		}
		ans=max(ans,sx+sy-max(sx*x,sy*y));
	}
	printf("%.10Lf\n",ans);
}
signed main(){
	int T=1;
	while(T--)sol(); 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 6072kb

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: 0
Accepted
time: 0ms
memory: 6104kb

input:

1
0 1

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

2
1 0
1 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 6044kb

input:

1
0.5 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

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

input:

3
0.4 100
0.6 100
0.6 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 6076kb

input:

3
0.2 100
0.2 100
0.8 100

output:

50.0000000000

result:

ok found '50.0000000', expected '50.0000000', error '0.0000000'

Test #8:

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

input:

2
0.999999 1000000
0.999998 2

output:

0.9999990000

result:

ok found '0.9999990', expected '0.9999990', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 6044kb

input:

2
0 100000
0.000001 1

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 6044kb

input:

2
0 1000000000
0.000001 1

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 552ms
memory: 36116kb

input:

1000000
0.375733 595197307
0.505261 377150668
0.517039 15795246
0.448099 228176467
0.529380 871983979
0.905546 876268308
0.095891 272104456
0.500302 916153337
0.128705 355768079
0.070600 78747362
0.444107 466118868
0.194987 298494965
0.462293 593292779
0.287909 838058266
0.237226 934603199
0.391909 ...

output:

85718080941203.0262451172

result:

ok found '85718080941203.0312500', expected '85718080941203.0156250', error '0.0000000'

Test #12:

score: 0
Accepted
time: 490ms
memory: 36532kb

input:

1000000
0.353000 999523129
0.526000 14560746
0.978000 319977952
0.324000 353889639
0.535500 497827437
0.153000 660990580
0.482000 391332319
0.050000 118814686
0.862500 774878817
0.417500 124874110
0.172500 789760737
0.058000 236910286
0.596000 585483625
0.176500 388072811
0.838000 806903092
0.613000...

output:

86000987369343.9291839600

result:

ok found '86000987369343.9218750', expected '86000987369343.9218750', error '0.0000000'

Test #13:

score: 0
Accepted
time: 467ms
memory: 35760kb

input:

1000000
0.200000 715833054
0.250000 346181893
0.700000 84047805
0.225000 911121283
0.575000 349964342
0.200000 472178743
0.400000 487500419
0.775000 358482180
0.525000 282051084
0.475000 664059239
0.350000 143371889
0.075000 768191797
0.025000 892648527
0.250000 266570522
0.175000 590192616
0.775000...

output:

90690663939242.5517272949

result:

ok found '90690663939242.5468750', expected '90690663939242.5468750', error '0.0000000'

Test #14:

score: 0
Accepted
time: 562ms
memory: 35364kb

input:

1000000
0.483249 58806278
0.092943 43698395
0.682093 234500498
0.899881 212323106
0.031970 94677621
0.248163 61052399
0.577708 189447689
0.737973 129234039
0.210538 112081344
0.451271 24559811
0.411130 846942
0.916990 268662655
0.992736 184750465
0.112959 105654084
0.932484 8474182
0.949654 21518817...

output:

16307385621417.6091079712

result:

ok found '16307385621417.6093750', expected '16307385621417.6074219', error '0.0000000'

Test #15:

score: 0
Accepted
time: 555ms
memory: 36152kb

input:

1000000
0.019963 244843587
0.361281 50413366
0.776551 132525209
0.435213 112540619
0.689322 261233354
0.023354 75471114
0.897100 120761316
0.650546 203049584
0.562689 213573846
0.606257 117745257
0.242362 401834266
0.331500 571471418
0.172223 291092482
0.713109 169535508
0.056464 106853676
0.068823 ...

output:

38012397725371.1932220459

result:

ok found '38012397725371.1953125', expected '38012397725371.1953125', error '0.0000000'

Test #16:

score: 0
Accepted
time: 512ms
memory: 35432kb

input:

1000000
0.299950 14454994
0.590800 131103748
0.168700 31811722
0.640950 153861933
0.097300 42347624
0.689900 25513183
0.313950 7694955
0.434400 41038786
0.992950 549929012
0.844350 177512169
0.193800 85807309
0.930300 78556126
0.920950 132277934
0.786750 282121687
0.420200 110220790
0.541000 9878024...

output:

18011656371809.6775932312

result:

ok found '18011656371809.6757812', expected '18011656371809.6757812', error '0.0000000'

Test #17:

score: 0
Accepted
time: 555ms
memory: 35476kb

input:

1000000
0.319563 16045815
0.898271 42370223
0.026295 36626864
0.009444 366071738
0.204970 43180228
0.686325 9473412
0.027009 25042313
0.659717 39445987
0.258480 45282965
0.472879 23682796
0.282075 8710935
0.512861 44842140
0.884086 10841294
0.600897 35981067
0.849081 41822205
0.643385 44337405
0.898...

output:

5561235835638.1348161697

result:

ok found '5561235835638.1347656', expected '5561235835638.1347656', error '0.0000000'

Test #18:

score: 0
Accepted
time: 512ms
memory: 36936kb

input:

1000000
0.253950 46
0.559560 542
0.009900 32083
0.403350 413
0.263990 425
0.921800 698
0.783520 455
0.530070 967
0.213120 478
0.050290 874
0.080430 599
0.992630 64
0.820820 475
0.595230 539
0.592450 290
0.393920 657
0.829040 339
0.831190 655
0.634960 910
0.991650 788
0.171040 707
0.599630 505
0.9605...

output:

1639467837.6792713404

result:

ok found '1639467837.6792715', expected '1639467837.6792715', error '0.0000000'

Test #19:

score: -100
Wrong Answer
time: 548ms
memory: 35552kb

input:

1000000
0.898172 7258266
0.104763 240434786
0.719320 63025017
0.422009 267258882
0.358730 246736331
0.183381 333433297
0.156389 498175665
0.797353 4106581
0.176858 677562755
0.519227 23114268
0.813408 17408292
0.661235 68857040
0.579091 35432878
0.451862 60091054
0.851985 8763380
0.508252 72544830
0...

output:

20247373451.7205785662

result:

wrong answer 1st numbers differ - expected: '20717770537103.9140625', found: '20247373451.7205772', error = '0.9990227'