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<set>
#include<iomanip>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#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
// if we know which collaborators to choose, it's better to choose the ones with smaller b first
void chmin(double &a, double x){
if (x<a) a=x;
}
ll n,k;
pii arr[505];
bool subtask1 = true, subtask2 = true;
// 看到第i個人,拿到了j票,目前people = p,最少時間
//double dp[505][505][505];
// 看到第i個人,選了j個B類
double dp[505][505];
bool comp(pii a, pii b){
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k;
int good=n;
for (int i=1;i<=n;i++) {
cin>>arr[i].first>>arr[i].second;
if (arr[i].second == -1) arr[i].second = 1e9, good--;
}
double best = 1e9;
sort(arr+1,arr+1+n,comp);
for (int goal=0;goal<=k;goal++){
if (goal>good) continue;
for (int i=0;i<=n+3;i++) for (int j=0;j<=n+3;j++) dp[i][j] = 1e9;
dp[1][0] = 1.0*arr[1].first/(goal+1); dp[1][1] = arr[1].second;
for (int i=1;i<k;i++) for (int j=0;j<goal;j++){
chmin(dp[i+1][j], dp[i][j] + 1.0*arr[i+1].first/(1+goal));
chmin(dp[i+1][j+1], dp[i][j] + 1.0*arr[i+1].second/(1+j));
}
double now = 1e9;
for (int pos=goal;pos<=k;pos++){ // position of last collaborator
vector<int> tmp;
for (int i=pos+1;i<=n;i++){ // 還要選k-pos個A類
tmp.push_back(arr[i].first);
}
sort(tmp.begin(),tmp.end());
double cost = 0;
for (int i=0;i<k-pos;i++) cost += 1.0*tmp[i];
cost /= (goal+1);
now = min(now, cost + dp[pos][goal]);
}
best = min(now, best);
}
cout<<fixed<<setprecision(9)<<best<<endl;
}
# | 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... |