C++11(clang++ 3.9) 解法, 执行用时: 70ms, 内存消耗: 1124K, 提交时间: 2020-06-21 18:29:40

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct pt
{
	int a,b;
}c[100005];
int n;
ll ans,p,q;
bool cmp(const pt x,const pt y)
{
	return 1ll*x.a*y.b>1ll*y.a*x.b;  //使用叉积可以避免浮点运算 
}
int main()
{
	scanf("%d%lld%lld",&n,&p,&q);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&c[i].a,&c[i].b);
	sort(c+1,c+n+1,cmp);
	ans=min(1ll*(c[n].b+c[n].a-1)/c[n].a*p,1ll*(c[1].a+c[1].b-1)/c[1].b*p+q); //特判 
	for(int i=1;i<n;i++)
	{
		pt u=c[i],v=c[i+1];
		if(1ll*u.a*v.b==1ll*v.a*u.b) continue;
		ll nw=0;
		while(1)
		{
			if(u.a>=u.b&&v.a>=v.b)  //case 1 
			{
				swap(u.a,u.b),swap(v.a,v.b);
				nw+=q;
			}
			else if(u.a<u.b&&v.a<v.b)  //case 2 
			{
				int ct=min((u.b-1)/u.a,(v.b-1)/v.a);
				u.b-=ct*u.a,v.b-=ct*v.a;
				nw+=ct*p;
			}
			else  //case 3 
			{
				if(u.a>=u.b) swap(u,v);
				ll nw1=0,nw2=0;
				pt w=u;
				w.b-=w.a;
				nw1=q+p+1ll*(w.a+w.b-1)/w.b*p;  //case 3.1
				if(v.a>v.b)
				{
					w=v;
					swap(w.a,w.b);
					w.b-=w.a;
					nw2=p+q*2+1ll*(w.a+w.b-1)/w.b*p;  //case 3.2
					nw1=min(nw1,nw2);
				}
				nw+=nw1;
				break;
			}
		}
		ans=min(ans,nw);
	}
	printf("%lld",ans);
	return 0;
}