Submission #8892855
Source Code Expand
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll N,K;
double w,p,l=0.0,r=100.0,mid;
vector<pair<double,double>> v;
bool check(double per, vector<pair<double,double>> vv){
double sumw,sums;
vector<pair<double,int>> prio;
rep(i,N){
prio.push_back({vv[i].first*(vv[i].second-per),i});
}
sort(ALL(prio),greater<pair<double,int>>());
rep(i,K){
sums+=vv[prio[i].second].first*vv[prio[i].second].second;
sumw+=vv[prio[i].second].first;
}
if((sums/sumw)>=per)return true;
else return false;
}
int main(){
cin>>N>>K;
rep(i,N){
cin>>w>>p;
v.push_back({w,p});
}
rep(i,200){
mid = (l+r)/2;
if(check(mid, v))l=mid;
else r=mid;
}
printf("%.12f\n",(l+r)/2.0);
}
Submission Info
Submission Time |
|
Task |
D - 食塩水 |
User |
submeryu |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1462 Byte |
Status |
WA |
Exec Time |
13 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s0.txt, s1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, s0.txt, s1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
WA |
13 ms |
256 KB |
001.txt |
WA |
2 ms |
256 KB |
002.txt |
WA |
12 ms |
256 KB |
003.txt |
WA |
2 ms |
256 KB |
004.txt |
WA |
13 ms |
256 KB |
005.txt |
WA |
12 ms |
256 KB |
006.txt |
WA |
12 ms |
256 KB |
007.txt |
WA |
10 ms |
256 KB |
008.txt |
WA |
13 ms |
256 KB |
009.txt |
WA |
2 ms |
256 KB |
010.txt |
WA |
13 ms |
256 KB |
011.txt |
WA |
6 ms |
256 KB |
012.txt |
WA |
13 ms |
256 KB |
013.txt |
WA |
5 ms |
256 KB |
014.txt |
WA |
13 ms |
256 KB |
015.txt |
WA |
10 ms |
256 KB |
016.txt |
WA |
13 ms |
256 KB |
017.txt |
WA |
8 ms |
256 KB |
018.txt |
WA |
13 ms |
256 KB |
019.txt |
WA |
9 ms |
256 KB |
s0.txt |
WA |
1 ms |
256 KB |
s1.txt |
WA |
1 ms |
256 KB |