Submission #1244135
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
#include <fstream>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
typedef long long ll;
ll N,A,B;
vector<double> v;
#define MOD 1000000000000000000
ll extgcd(ll a, ll b, ll& x, ll& y) {
if(b==0){
x=(a>=0)?1:-1;
y=0;
return abs(a);
}else{
ll res=extgcd(b,a%b,y,x);
y-=(a/b)*x;
return res;
}
}
ll mod_inverse(ll a, ll m) {
ll x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
ll c(ll n, ll k) {
ll res=1;
for(int i=0;i<k;i++)res=(res*((n-i)%MOD))%MOD;
for(int i=1;i<=k;i++)res=(res*mod_inverse(i,MOD))%MOD;
return res;
}
int main() {
cin >> N >> A >> B;
v.resize(N);
REP(i,N) cin >> v[i];
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
double ave = 0.0;
double sum = 0.0;
int cnt = -1;
REP(i,B) {
if(i<A-1) sum += v[i];
else {
sum += v[i];
double avet = sum / ((double)(i + 1));
if(ave <= avet) {
ave = avet;
cnt = i+1;
}
}
}
cout << fixed << setprecision(10) << ave << endl;
map<double,int> cntm;
REP(i,cnt) cntm[v[i]]++;
ll ko = cntm[ave];
ll s = cnt - A;
ll ans = 0;
for(ll i=0;i<=s;i++){
ans += c(ko,i);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Maximum Average Sets |
User |
kosakkun |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2105 Byte |
Status |
WA |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
WA |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
WA |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
WA |
1 ms |
256 KB |
subtask_1_11.txt |
WA |
1 ms |
256 KB |
subtask_1_12.txt |
WA |
1 ms |
256 KB |
subtask_1_13.txt |
WA |
1 ms |
256 KB |
subtask_1_14.txt |
WA |
1 ms |
256 KB |
subtask_1_15.txt |
WA |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_3.txt |
AC |
1 ms |
256 KB |
subtask_1_4.txt |
AC |
1 ms |
256 KB |
subtask_1_5.txt |
AC |
1 ms |
256 KB |
subtask_1_6.txt |
WA |
1 ms |
256 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
WA |
1 ms |
256 KB |
subtask_1_9.txt |
WA |
1 ms |
256 KB |