Submission #67746502

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    int m;
    cin >> n >> m;
    vector<long long> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }
    vector<tuple<long long, double, long long, long long>> C;
    for (int i = 0; i < m; i++) {
        double efficiency = (double)b[i] / a[i];
        C.emplace_back(b[i] - a[i], efficiency, a[i], b[i]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    int m;
    cin >> n >> m;
    vector<long long> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }


    vector<tuple<long long, double, long long, long long>> C;
    for (int i = 0; i < m; i++) {
        double efficiency = (double)b[i] / a[i];
        C.emplace_back(b[i] - a[i], efficiency, a[i], b[i]);
    }
    sort(C.begin(), C.end(), [](auto &x, auto &y) {
        if (get<0>(x) != get<0>(y)) return get<0>(x) > get<0>(y);
        return get<1>(x) > get<1>(y);
    });

    long long full = n;
    long long emp = 0;
    long long answer = 0;

    while (true) {
        emp += full;
        full = 0;
        bool ex = false;
        for (auto &[diff, eff, A, B] : C) {
            if (emp >= A) {
                long long times = emp / A;
                emp -= times * A;
                full += times * B;
                answer += times;
                ex = true;
                break;
            }
        }
        if (!ex) break;
    }

    cout << answer << "\n";
    return 0;
}

Submission Info

Judge Result