比赛 |
2012Day1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
国王游戏 |
最终得分 |
100 |
用户昵称 |
stdafx.h |
运行时间 |
0.158 s |
代码语言 |
C++ |
内存使用 |
0.35 MiB |
提交时间 |
2015-10-22 19:31:53 |
显示代码纯文本
#define MAXN 4010UL
#include <cstdio>
#include <algorithm>
#include <cstring>
struct Point{
int l,r;
inline void in(){scanf("%d%d",&l,&r);return;}
};
struct BigNum{
int s[MAXN];
inline void clr(){memset(s,0,sizeof(s));return;}
inline void setnum(int p){clr();while(p) s[++s[0]]=p%10,p/=10;return;}
inline void prx(){for(int i=s[0];i>0;i--) putchar(s[i]+48);return;}
friend BigNum operator * (BigNum temp_a,BigNum temp_b){
BigNum temp_c;temp_c.clr();int i,j,x,*a=temp_a.s,*b=temp_b.s,*c=temp_c.s;
for(c[0]=a[0]+b[0]+1,i=1;i<=a[0];c[i+b[0]]=x,i++) for(j=1,x=0;j<=b[0];j++) c[i+j-1]+=a[i]*b[j]+x,x=c[i+j-1]/10,c[i+j-1]%=10;
while((!c[c[0]])&&c[0]>1) --c[0];return temp_c;
}
friend BigNum operator / (BigNum temp_a,int b){
BigNum temp_c;temp_c.clr();int i,j,x=0,*a=temp_a.s,*c=temp_c.s;
for(c[0]=i=a[0];i>0;x=(x<<1)+(x<<3),i--) c[i]=(a[i]+x)/b,x=(a[i]+x)%b;
while((!c[c[0]])&&c[0]>1) --c[0];return temp_c;
}
friend bool operator > (BigNum temp_a,BigNum temp_b){
if(temp_a.s[0]!=temp_b.s[0]) return temp_a.s[0]>temp_b.s[0];
for(int i=temp_a.s[0];i>0;i--) if(temp_a.s[i]!=temp_b.s[i]) return temp_a.s[i]>temp_b.s[i];
return false;
}
};
Point s[MAXN];
int n;
inline int MAX(int a,int b){return a>b?a:b;}
inline bool comp(Point a,Point b){return MAX(b.r,a.l*a.r)<MAX(a.r,b.l*b.r);}
BigNum Ans,Cm;
int main(){
freopen("kinggame.in","r",stdin);freopen("kinggame.out","w",stdout);
scanf("%d",&n);n++;for(int i=0;i<n;i++) s[i].in();std::sort(s+1,s+n,comp);
Cm.setnum(s[0].l);
for(int i=1;i<n;i++){
BigNum temp,res;
res=Cm/s[i].r;
if(res>Ans) Ans=res;
temp.setnum(s[i].l);
Cm=Cm*temp;
}
Ans.prx();
return 0;
}