比赛 2012Day1 评测结果 AAAAAAAAAA
题目名称 国王游戏 最终得分 100
用户昵称 阿狸 运行时间 1.147 s
代码语言 C++ 内存使用 15.91 MiB
提交时间 2015-10-22 19:30:42
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;
const ll MOD=1000000;
int n;
int l,r;
struct edge{
	ll l,r;
}q[1000100];
struct node{
	int l;
	ll k[10100];
}ans;
int com(edge a,edge b){
	if(a.l*a.r==b.l*b.r)return a.l<b.l;
	return a.l*a.r<b.l*b.r;
}

node C1(node a,int x){
	node c=a;
	for(int i=c.l;i>=1;--i){
		c.k[i-1]+=c.k[i]%x*MOD;
		c.k[i]=c.k[i]/x;
	}
	c.k[0]=0;
	while(c.k[c.l]==0&&c.l)c.l--;
	return c;
}
node C2(node a,int x){
	node c=a;
	for(int i=1;i<=c.l;++i)c.k[i]=c.k[i]*x;
	for(int i=1;i<c.l;++i){
		if(c.k[i]>=MOD){
			c.k[i+1]+=c.k[i]/MOD;
			c.k[i]%=MOD;
		}
	}
	while(c.k[c.l]>=MOD){
		c.k[c.l+1]+=c.k[c.l]/MOD;
		c.k[c.l]%=MOD;
		c.l++;
	}
	return c;
}
node M(node a,node b)
{
	if(a.l>b.l)return a;
	else if(a.l<b.l)return b;
	else{
		for(int i=a.l;i>=1;--i)
		    if(a.k[i]>b.k[i])return a;
		    else if(a.k[i]<b.k[i])return b;
		    else continue;
	}
	return a;
}
int main()
{
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout);
	cin>>n;cin>>l>>r;
	node a;
	memset(a.k,0,sizeof(a.k));
	memset(ans.k,0,sizeof(ans.k));
	a.l=1;
	a.k[1]=l;
	ans.l=0;
	for(int i=1;i<=n;++i)
    	cin>>q[i].l>>q[i].r;
	sort(q+1,q+n+1,com);
	for(int i=1;i<=n;++i)
	{
		node b=C1(a,q[i].r);
		ans=M(ans,b);
		a=C2(a,q[i].l);
	}
	printf("%lld",ans.k[ans.l]);
	for(int i=ans.l-1;i>=1;--i)printf("%06d",ans.k[i]);
	return 0;
}