QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#747059 | #8037. Gambler's Ruin | Uraboku | WA | 1ms | 8044kb | C++23 | 2.2kb | 2024-11-14 16:15:37 | 2024-11-14 16:15:38 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define O4 __inline__ __attribute__((always_inline))
#define UL unsigned LL
#define LD long double
//#ifdef ONLINE_JUDGE
//#define getchar nc
//#endif
//#define int LL
namespace FastIO{
O4 char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
O4 int read(){
char t;int u=0,k=1;t=getchar();
while(t<'0'||t>'9'){if(t==EOF)return -233;if(t=='-')k=-1;t=getchar();}
while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
return u*k;
}
template <typename T>
O4 void read(T &u){
char t;T k=1;u=0;t=getchar();
while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
if(t=='.'){
T mass=0.1;t=getchar();
while(t>='0'&&t<='9'){u+=mass*(t-'0');mass/=10;t=getchar();}
}u*=k;
}
O4 int read(char asd[]){
char t=getchar();int u=0;
while(t==' '||t=='\n'||t=='\r')t=getchar();
if(t==EOF)return -1;
while(t!=' '&&t!='\n'&&t!=EOF&&t!='\r')asd[u++]=t,t=getchar();
asd[u]='\0';return u;
}
char sr[1<<23],z[23];int C=-1,Z;
O4 void wer(int x,char T){
int y=0;if(x<0)y=1,x=-x;
while(z[++Z]=x%10+'0',x/=10);if(y)z[++Z]='-';
while(sr[++C]=z[Z],--Z);sr[++C]=T;
}
O4 void wer(char T[],char QWQ){
for(int i=0;T[i]!='\0';i++)sr[++C]=T[i];
sr[++C]=QWQ;
}
O4 void out(){fwrite(sr,1,C+1,stdout);C=-1;}
}
using namespace std;
using namespace FastIO;
const int N=1e6+5;
int n,m,a,b,c,d,e,limit,k;
struct sss{
double p;
int c;
}tk[N];
LL pre[N],suf[N];
double cx(int x){
return pre[x]/tk[x].p;
}
double cy(int y){
return suf[y]/(1-tk[y].p);
}
const double eps=1e-7;
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%d",&tk[i].p,&tk[i].c);
}
sort(tk+1,tk+1+n,[](sss a,sss b){return a.p>b.p;});
int tp=n;n=0;
for(int i=1;i<=tp;i++){
if(abs(tk[i].p-tk[i-1].p)<eps)tk[n].c+=tk[i].c;
else tk[++n]=tk[i];
}
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+tk[i].c;
for(int i=n;i;i--)suf[i]=suf[i+1]+tk[i].c;
int pos=n;
double ans=-1e233;
for(int i=1;i<=n;i++){
while(pos!=0&&cx(i)>cy(pos))pos--;
ans=max(ans,pre[i]+suf[pos+1]-cx(i));
if(pos!=0)ans=max(ans,pre[i]+suf[pos]-cy(pos));
}
printf("%.10lf",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8044kb
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: 0ms
memory: 8000kb
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: 1ms
memory: 8000kb
input:
1 0 1
output:
-99999999999999997374062707399103193390970327051935144057886852787877127050853725394623645022622268104986814019040754458979257737456796162759919727807229498567311142603806310797883499542489243201826933949562808949044795771481474727936.0000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '-99999999999999997374062707399103193390970327051935144057886852787877127050853725394623645022622268104986814019040754458979257737456796162759919727807229498567311142603806310797883499542489243201826933949562808949044795771481474727936....