QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#747059#8037. Gambler's RuinUrabokuWA 1ms8044kbC++232.2kb2024-11-14 16:15:372024-11-14 16:15:38

Judging History

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

  • [2024-11-14 16:15:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8044kb
  • [2024-11-14 16:15:37]
  • 提交

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....