#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
struct Minister {
    int left, right;
};
 
bool compare(const Minister &a, const Minister &b) {
    return a.left  * a.right  < b.left  * b.right; 
}
 
string multiply(string num1, int num2) {
    string res;
    int carry = 0;
    for (int i = num1.size()  - 1; i >= 0; --i) {
        int product = (num1[i] - '0') * num2 + carry;
        res.push_back(product  % 10 + '0');
        carry = product / 10;
    }
    while (carry) {
        res.push_back(carry  % 10 + '0');
        carry /= 10;
    }
    reverse(res.begin(),  res.end()); 
    return res;
}
 
string divide(string num, int divisor) {
    string res;
    int idx = 0;
    int temp = num[idx] - '0';
    while (temp < divisor && idx + 1 < num.size())  {
        temp = temp * 10 + (num[++idx] - '0');
    }
    while (idx < num.size())  {
        res += (temp / divisor) + '0';
        temp = (temp % divisor) * 10 + (++idx < num.size()  ? num[idx] - '0' : 0);
    }
    return res.empty()  ? "0" : res;
}
 
bool greaterThan(const string &a, const string &b) {
    if (a.size()  != b.size())  return a.size()  > b.size(); 
    return a > b;
}
 
int main() {
    int n;
    cin >> n;
    int kingLeft, kingRight;
    cin >> kingLeft >> kingRight;
    
    vector<Minister> ministers(n);
    for (int i = 0; i < n; ++i) {
        cin >> ministers[i].left >> ministers[i].right;
    }
    
    sort(ministers.begin(),  ministers.end(),  compare);
    
    string maxReward = "0";
    string product = to_string(kingLeft);
    
    for (int i = 0; i < n; ++i) {
        string reward = divide(product, ministers[i].right);
        if (greaterThan(reward, maxReward)) {
            maxReward = reward;
        }
        product = multiply(product, ministers[i].left);
    }
    
    cout << maxReward << endl;
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
465
时间
1000ms
内存
256MiB
难度
9
标签
递交数
13
已通过
3
上传者