제출 #105881

#제출 시각아이디문제언어결과실행 시간메모리
105881leonardaPareto (COCI17_pareto)C++14
20 / 80
66 ms5468 KiB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 3 * 1e5;

int n;
int a[maxn];
lint sum[maxn];
double maks;
double x, y;

bool komp(int t1, int t2) {
	return t2 < t1;
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n;  ++i)
		cin >> a[i];
	
	sort(a, a + n, komp);
  
	sum[0] = a[0];
	for(int i = 1; i < n; ++i)
		sum[i] = sum[i - 1] + a[i];
	
	int lo = 0, hi = n - 1;
	while(lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		double pare = (double)sum[mid] / (double)sum[n - 1] * 100;
		double postotak = (double)(mid + 1) / (double)n * 100;
		if(pare - postotak > maks) {
			maks = pare - postotak;
			x = pare;
			y = postotak;
			hi = mid - 1;
		}
		else
			lo = mid + 1;
	}
	
	cout << setprecision(10) << y << endl << setprecision(10) << x;

return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...