Submission #1185183
Source Code Expand
#include <iostream> #include <vector> #include <cmath> using namespace std; typedef long long ll; typedef long double ld; const ld eps=1e-9; ll dp[64][64]; ll dp2[64][64]; int main(){ int n,a,b; cin>>n>>a>>b; vector<ll> v(n); for(int i=0;i<n;i++) cin>>v[i]; dp2[0][0]=1; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ if(dp[i+1][j]<dp[i][j]){ dp[i+1][j]=dp[i][j]; dp2[i+1][j]=dp2[i][j]; } else if(dp[i+1][j]==dp[i][j]){ dp2[i+1][j]+=dp2[i][j]; } if(dp[i+1][j+1]<dp[i][j]+v[i]){ dp[i+1][j+1]=dp[i][j]+v[i]; dp2[i+1][j+1]=dp2[i][j]; } else if(dp[i+1][j+1]==dp[i][j]+v[i]){ dp2[i+1][j+1]+=dp2[i][j]; } } } ld ret=0; for(int i=a;i<=b;i++) ret=max(ret,(ld)dp[n][i]/i); printf("%.15Lf\n",ret); ll pattern=0; for(int i=a;i<=b;i++){ if(fabs(ret-(ld)dp[n][i]/i)<eps) pattern+=dp2[n][i]; } printf("%Ld\n",pattern); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Maximum Average Sets |
User | fiord |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 930 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 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 | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
sample_04.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 256 KB |
subtask_1_10.txt | AC | 1 ms | 256 KB |
subtask_1_11.txt | AC | 1 ms | 256 KB |
subtask_1_12.txt | AC | 1 ms | 256 KB |
subtask_1_13.txt | AC | 1 ms | 256 KB |
subtask_1_14.txt | AC | 1 ms | 256 KB |
subtask_1_15.txt | AC | 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 | AC | 1 ms | 256 KB |
subtask_1_7.txt | AC | 1 ms | 256 KB |
subtask_1_8.txt | AC | 1 ms | 256 KB |
subtask_1_9.txt | AC | 1 ms | 256 KB |