Submission #593589

#	Time	Username	Problem	Language	Result	Execution time	Memory
593589		piOOE	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	2 ms	332 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long double;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n), oa(n), ob(n);
    int cntb = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        if (b[i] != -1) {
            cntb += 1;
        }
    }
    iota(oa.begin(), oa.end(), 0), iota(ob.begin(), ob.end(), 0);
    sort(oa.begin(), oa.end(), [&a](int i, int j) {
        return a[i] < a[j];
    });
    sort(ob.begin(), ob.end(), [&](int i, int j) {
        if (b[i] == -1) return false;
        if (b[j] == -1) return true;
        return b[i] < b[j];
    });
    const db inf = 1e9;
    db ans = inf;
    for (int cnt = 0; cnt <= min(k, cntb); ++cnt) {
        vector<bool> used(n);
        db now = 0;
        int done = 0;
        for (int i = 0; i < cnt; ++i) {
            now += b[ob[i]] / (db(i + 1));
            used[ob[i]] = true;
            done += 1;
        }
        for (int i = 0; i < n && done < k; ++i) {
            if (!used[oa[i]]) {
                done += 1;
                now += a[oa[i]] / (db(cnt + 1));
            }
        }
        assert(done >= k);
        ans = min(ans, now);
    }
    cout << fixed << setprecision(20) << ans;
    return 0;
}

• 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