Submission #2374269

Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define TO_INT(vec,s) REP(i,s.length()){vec.push_back(s[i] - ‘0’);}
#define ENUM_v(vec) for (auto e : vec)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())

using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;
typedef pair<long,long> pr;
typedef vector<pr> VP;
typedef vector<VP> VVP;

int main(void) {
	long N,K;
	cin >> N >> K;
	vector<double> eval(N),w(N),p(N);
	REP(i,N) cin >> w[i] >> p[i];
	double l = 0.0;
	double r = 100.0;
	double mid;
	double sum;
	REP(i,100) {
		mid = (r + l)/2.0;
		REP(i,N) eval[i] = ((p[i]/100.) * w[i]) - ((mid/100.) * w[i]);
		SORT(eval);
		sum = 0.;
		REP(i,K) sum += eval[N-i-1];
		if (sum >= 0.) l = mid;
		else r = mid;
	}
	cout << setprecision(8) << l << endl;
	return 0;
}

Submission Info

Submission Time
Task D - 食塩水
User banboooo044
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1956 Byte
Status
Exec Time 6 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s0.txt, s1.txt
All 100 / 100 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 6 ms 256 KB
001.txt 2 ms 256 KB
002.txt 6 ms 256 KB
003.txt 2 ms 256 KB
004.txt 6 ms 256 KB
005.txt 6 ms 256 KB
006.txt 6 ms 256 KB
007.txt 5 ms 256 KB
008.txt 6 ms 256 KB
009.txt 1 ms 256 KB
010.txt 6 ms 256 KB
011.txt 3 ms 256 KB
012.txt 6 ms 256 KB
013.txt 3 ms 256 KB
014.txt 6 ms 256 KB
015.txt 5 ms 256 KB
016.txt 6 ms 256 KB
017.txt 4 ms 256 KB
018.txt 6 ms 256 KB
019.txt 4 ms 256 KB
s0.txt 1 ms 256 KB
s1.txt 1 ms 256 KB