Submission #890697

#	Time	Username	Problem	Language	Result	Execution time	Memory
890697		arbuzick	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1677 ms	600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    vector<pair<int, int>> s_a;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        s_a.emplace_back(a[i], i);
    }
    sort(s_a.begin(), s_a.end());
    long double ans = 1e9 + 7;
    for (int pr_a = 0; pr_a <= k; ++pr_a) {
        for (int cnt_b = k - pr_a; cnt_b < k; ++cnt_b) {
            vector<int> used(n);
            long double ans_nw = 0;
            for (int i = 0; i < pr_a; ++i) {
                used[s_a[i].second] = 1;
                ans_nw += s_a[i].first / (double)(cnt_b + 1);
            }
            vector<double> s_b1;
            vector<pair<double, double>> s_b2;
            for (int i = 0; i < n; ++i) {
                if (b[i] != -1 && !used[i]) {
                    s_b1.push_back(b[i]);
                } else if (b[i] != -1) {
                    s_b2.emplace_back(b[i], a[i] / (double)(cnt_b + 1));
                }
            }
            sort(s_b1.begin(), s_b1.end());
            sort(s_b2.begin(), s_b2.end());
            if (s_b1.size() + s_b2.size() < cnt_b) {
                continue;
            }
            int pos1 = 0, pos2 = 0;
            int cnt = pr_a;
            int cnt_b_vl = 0;
            double speed = 1;
            while (cnt < k || cnt_b_vl < cnt_b) {
                if (pos1 < (int)s_b1.size() && pos2 < (int)s_b2.size()) {
                    if (s_b1[pos1] / speed < s_b2[pos2].first / speed - s_b2[pos2].second) {
                        ans_nw += s_b1[pos1] / speed;
                        cnt++;
                        pos1++;
                        cnt_b_vl++;
                        speed += 1;
                    } else {
                        ans_nw += s_b2[pos2].first / speed - s_b2[pos2].second;
                        pos2++;
                        cnt_b_vl++;
                        speed += 1;
                    }
                } else if (pos1 < (int)s_b1.size()) {
                    ans_nw += s_b1[pos1] / speed;
                    cnt++;
                    pos1++;
                    cnt_b_vl++;
                    speed += 1;
                } else if (pos2 < (int)s_b2.size()) {
                    ans_nw += s_b2[pos2].first / speed - s_b2[pos2].second;
                    pos2++;
                    cnt_b_vl++;
                    speed += 1;
                } else {
                    break;
                }
            }
            if (cnt >= k && cnt_b_vl >= cnt_b) {
                ans = min(ans, ans_nw);
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(25);
    cout << fixed;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:35:43: warning: comparison of integer expressions of different signedness: 'std::vector<double>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |             if (s_b1.size() + s_b2.size() < cnt_b) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23