Submission #534210

#	Time	Username	Problem	Language	Result	Execution time	Memory
534210		Cookie197	Let's Win the Election (JOI22_ho_t3)	C++14	23 / 100	2563 ms	312 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define endl "\n"
#define out(x) cout << #x << " = " << x << endl
#define outp(x) cout << #x << ".first = " << x.first << "  " << #x << ".second = " << x.second << endl
#pragma GCC optimize("Ofast")
#define lll __int128

// enumerate the num of collaborators, from 0 to k-1
// it is optimal to collect all collaborators first, then give speeches

int n,k;
pii arr[505];

signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
    for (int i=0;i<n;i++) cin>>arr[i].first>>arr[i].second;

    double best = 1e9;
    int ok[505];
    vector<int> collab,speech;
    for (int bit=0;bit<(1<<n);bit++){ // choose collaborators
        if (__builtin_popcount(bit) >= k) continue;
        double now = 0;
        collab.clear();
        for (int i=0;i<n;i++) ok[i] = false;
        int cnt = 0;
        for (int i=0;i<n;i++) if ((1<<i) & bit){
            if (arr[i].second != -1) collab.push_back(arr[i].second), ok[i] = true, cnt++;
        }
        sort(collab.begin(),collab.end());
        int people = 1;
        for (double d:collab){
            now += d/people;
            people++;
        }

        speech.clear();
        for (int i=0;i<n;i++) if (!ok[i]){
            speech.push_back(arr[i].first);
        }

        sort(speech.begin(),speech.end());
        for (int i=0;i<k-cnt;i++){
            now += 1.0 * speech[i] / people;
        }

        best = min(best, now);
    }
    cout<<fixed<<setprecision(9)<<best<<endl;
}

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