Submission #1268064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268064		ChuanChen	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	4 ms	328 KiB

Main

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

const int inf = 2e9;
int n, k;
vector<pair<int, int>> states;

bool cmp(pair<int, int> x, pair<int, int> y) {
    if (x.second == y.second) return x.first > y.first;
    return x.second < y.second;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (b == -1) b = inf;
        states.push_back({a, b});
    }
    sort(states.begin(), states.end(), cmp);
    long double ans = inf;
    for (int T = 0; T <= k; T++) {
        if (T > 0 && states[T-1].second == inf) break;
        long double spent = 0;
        int efficiency = 1;
        for (int i = 0; i < T; i++) {
            spent += states[i].second / (long double) efficiency;
            efficiency++;
        }
        vector<int> left_over;
        for (int i = T; i < n; i++) {
            left_over.push_back(states[i].first);
        }
        sort(left_over.begin(), left_over.end());
        int sum = 0;
        for (int i = 0; i < k - T; i++) {
            sum += left_over[i];
        }
        spent += sum / (long double) efficiency;
        if (ans > spent) ans = spent;
    }
    cout << fixed << setprecision(16) << ans << endl;
    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