This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
bool subtask1 = true, subtask2 = true;
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;
if (arr[i].second != -1) subtask1 = false;
if (arr[i].second != -1 && arr[i].second != arr[i].first) subtask2 = false;
}
if (subtask1){
sort(arr,arr+n);
int ans = 0;
for (int i=0;i<k;i++) ans+=arr[i].first;
cout<<ans<<endl;
return 0;
}
if (n<=20){
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;
return 0;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |