# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
534130 | 2022-03-08T01:24:45 Z | PikaQ | Let's Win the Election (JOI22_ho_t3) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define forn(i,n) for(int i = 0;i < (n);i++) #define Forn(i,n) for(int i = 1;i <= (n);i++) #define all(p) p.begin(),p.end() #define pb push_back #define F first #define S second #define rz resize #define sz(x) x.size() #define int long long #define vi vector<int> #define pii pair<int,int> using namespace std; const int N = 2e5+9; const int INF = 1e9+9; int n,k; vector<pii> a; void solve(){ cin >> n >> k; a.rz(n); forn(i,n){ cin >> a[i].S >> a[i].F; if(a[i].F == -1) a[i].F = INF; } sort(all(a)); double ans = INF; double res = 0; for(int i = 0;i <= k;i++){ if(i) { res += (double) a[i-1].F/i; } vi b; for(int j = i;j < n;j++){ b.pb(a[j].S); } sort(all(b)); int tr = 0; for(int r = 0;r < k-i;r++){ tr += b[r]; } ans = min(ans,(double) res + (double) / (i+1)); } cout << ans << '\n'; } signed main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(0); solve(); return 0; }