Submission #1183579

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
int N,A,B;
ll v[60];
ii dp[60];

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

double calc_max() {
  sort(v,v+N,greater<ll>());
  double maxi = 0;
  REP(i,A,B+1) {
    ll sum = 0;
    rep(j,i) sum += v[j];
    if( LT(maxi,sum/(double)i) ) {
      maxi = sum/(double)i;
      //cout << sum << " / " << i << " = ";
      //printf("%.10f\n",maxi);
    }
  }
  return maxi;
}

int main() {
  if( 0 ) {
    cout << 50 << " " << 25 << " " << 50 << endl;
    rep(i,50) {
      if( i == 0 ) {
	cout << 2 << endl;
      } else {
	cout << 1 << endl;
      }
    }
    return 0;
  }
  cin >> N >> A >> B;
  rep(i,N) cin >> v[i];
  double maxi = calc_max();
  printf("%.10f\n",maxi);
  ll cnt = 0;
  rep(j,N+1) dp[j] = ii(0,0);
  dp[0] = ii(0,1);

  rep(j,N) {
    for(int k=N;k>=0;--k) {
      if( dp[k+1].first < dp[k].first + v[j] ) {
	dp[k+1].first = dp[k].first + v[j];
	dp[k+1].second = dp[k].second;
      } else if( dp[k+1].first == dp[k].first + v[j] ) {
	dp[k+1].second += dp[k].second;
      }
    }
  }
  REP(j,A,B+1) {
    //puts("");
    //cout << dp[j].first << " / " << j << endl;
    //printf("%.10f\n",dp[j].first/(double)j);
    //cout << dp[j].second << endl;
    if( equals(maxi,dp[j].first/(double)j) ) {
      //cout << "IN" << endl;
      cnt += dp[j].second;
    }
  }
  cout << cnt << endl;
  return 0;
}

Submission Info

Judge Result