#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif
#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++)
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MOD=1e9+7;
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
ll n,k;
cin>>n>>k;
vpll v(n);
REP(i,n){
cin>>v[i].ff>>v[i].ss;
}
vpll speak, win;
REP(i,n){
win.pb({v[i].ff,i});
if(v[i].ss!=-1) speak.pb({v[i].ss, i});
}
sort(all(win));
sort(all(speak));
ll s=speak.size();
auto check=[&](double x){
for(ll cnt=0; cnt<=s; cnt++){
double t=x, sm=0;
set<ll> used;
REP(i, cnt){
used.insert(speak[i].ss);
sm+=speak[i].ff;
t-=speak[i].ff;
t+=x-sm;
}
ll left=k-cnt;
ll p=0;
while(left){
if(!contains(used, win[p].ss)){
left--;
t-=win[p].ff;
}
p++;
}
if(t>=0) return true;
}
return false;
};
double l=0, r=1e6;
while(r-l>1e-6){
double mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid;
}
}
cout<<r<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
379 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
| 13 |
Halted |
0 ms |
0 KB |
- |
