QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661758 | #8037. Gambler's Ruin | MENDAX | WA | 791ms | 37148kb | C++20 | 1.0kb | 2024-10-20 17:59:05 | 2024-10-20 17:59:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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 c[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;
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){
if(i>r)break;
sx+=a[i].c;
if(a[i].p==a[i+1].p)continue;
long double x=1/a[i].p;
while(r>i){
int ssy=sy+a[r].c;
long double yy=1/(1-a[r].p);
if(ssy-max(sx*x,ssy*yy)>sy-max(sx*x,sy*y))sy=ssy,y=yy,--r;
else break;
}
while(r>i&&a[r].p==a[r+1].p)sy+=a[r].c,--r;
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: 5904kb
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: 5876kb
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: 1ms
memory: 6028kb
input:
1 0 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5952kb
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: 1ms
memory: 6072kb
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: 0ms
memory: 6024kb
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: 1ms
memory: 6056kb
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: 6028kb
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: 1ms
memory: 6028kb
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: 1ms
memory: 6080kb
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: 791ms
memory: 36464kb
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: 739ms
memory: 36900kb
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: 709ms
memory: 35788kb
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: 772ms
memory: 35252kb
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: 767ms
memory: 36448kb
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: 744ms
memory: 37148kb
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: 745ms
memory: 35708kb
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: 632ms
memory: 36760kb
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: 767ms
memory: 37024kb
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:
10183147483.8420182653
result:
wrong answer 1st numbers differ - expected: '20717770537103.9140625', found: '10183147483.8420181', error = '0.9995085'