比赛 五一大礼包 评测结果 AAAAWWWWWA
题目名称 国王游戏 最终得分 50
用户昵称 LikableP 运行时间 0.425 s
代码语言 C++ 内存使用 3.88 MiB
提交时间 2026-05-04 11:52:00
显示代码纯文本
#include <cstdio>
#include <algorithm>
typedef long long ll;

const int MAXN = 1010;

int n;
struct { ll a, b; } a[MAXN];

int main() {
  freopen("kinggame.in", "r", stdin);
  freopen("kinggame.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 0; i <= n; ++i) scanf("%lld %lld", &a[i].a, &a[i].b);
  
  if (n <= 10) {
    int *order = new int[n + 1];
    for (int i = 0; i <= n; ++i) order[i] = i;
    ll ans = 0x7fffffffffffffff;
    do {
      ll mul = 1, maxx = -1;
      for (int i = 0; i <= n; ++i) {
        if (i) maxx = std::max(maxx, mul / a[order[i]].b);
        mul *= a[order[i]].a;
      }
      ans = std::min(ans, maxx);
    } while (std::next_permutation(order + 1, order + n + 1));
    printf("%lld\n", ans);
    return 0;
  }
  
  std::sort(a + 1, a + n + 1, [](auto x, auto y) {
    return x.b < y.b;
  });
  
  ll mul = 1, maxx = -1;
  for (int i = 0; i <= n; ++i) {
    if (i) maxx = std::max(maxx, mul / a[i].b);
    mul *= a[i].a;
  }
  
  printf("%lld\n", maxx);
  return 0;
}