记录编号	301864	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]国王游戏	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2016-09-02 18:05:04	内存使用	38.65 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e4 + 10;
const int base = 1e4;
const int inf = 1e9;

int n;

#define is_num(x) (x <= '9' and x >= '0')
int get_num() {
	char tmp = getchar();
	int res = 0;
	while(not is_num(tmp)) tmp = getchar();
	while(    is_num(tmp)) {
		res = res * 10 + tmp - '0';
		tmp = getchar();
	}
	return res;
}

struct BigNum {
	int a[1000];
	
	BigNum() { memset(a, 0, sizeof(a)); }
	BigNum(int num) {
		memset(a, 0, sizeof(a));
		int now = 1;
		while(num) {
			a[now] = num % base;
			num /= base;
			now++;
		}
		a[0] = now - 1;
	}
	
	BigNum operator *= (const int b) {
		int le = 0;
		for(int i = 1; i <= a[0]; i++) {
			a[i] = a[i] * b + le;
			le = a[i] / base;
			a[i] %= base;
		}
		while(le) a[++a[0]] = le % base, le /= base;
		while(a[0] > 1 and not a[a[0]]) a[0]--;
	}
	
	BigNum operator /= (const int b) {
		for(int i = a[0]; i >= 2; i--) {
			a[i - 1] += a[i] % b * base;
			a[i] /= b;
		}
		a[1] /= b;
		while(a[0] > 1 and not a[a[0]]) a[0]--;
	}
	
	bool operator < (const BigNum &b) const {
		if(a[0] < b.a[0]) return true;
		for(int i = a[0]; i >= 1; i--) if(a[i] < b.a[i]) return true;
		return false;
	}
	
	void out() { printf("%d", a[a[0]]); for(int i = a[0] - 1; i >= 1; i--) printf("%04d", a[i]); }
};

struct People {
	int l, r;
	LL mul;
	People() {}
	People(int l_, int r_) { l = l_, r = r_, mul = 1ll * l * r; }
	
	bool operator < (const People & b) const { return mul < b.mul; }
}ps[maxn];

void read() {
	n = get_num();
	int l, r;
	l = get_num();
	r = get_num();
	ps[0] = People(l, r);
	for(int i = 1; i <= n; i++)
		l = get_num(), r = get_num(), ps[i] = People(l, r);
}

BigNum f[maxn], ans;

void solve() {
	sort(ps + 1, ps + 1 + n);
	BigNum mul = BigNum(ps[0].l);
	BigNum tmp;
	for(int i = 1; i <= n; i++) {
		tmp = mul, tmp /= ps[i].r;
		if(ans < tmp) ans = tmp;
		mul *= ps[i].l;
	}
	ans.out();
}

int main() {
	freopen("kinggame.in", "r", stdin);
	freopen("kinggame.out", "w", stdout);
	read();
	solve();
	return 0;
}