比赛 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;
}