fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <deque>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8. const LL INF = 1000000000000000007ll;
  9. typedef pair<int,LL> PIL;
  10.  
  11. int n,m,l,r,a[100005];
  12. LL  dp[11][100005],sum[100005],pfx[100005];
  13. PIL pt[11][100005];
  14.  
  15. bool gao(LL& num, LL& den){
  16.     for(int i=0;i<n;i++) sum[i+1]=sum[i]+a[i]*den-num;
  17.     for(int old=0;old<m;old++){
  18.         int now=1+old;
  19.         dp[now][0]=-INF;
  20.         deque<PIL> u;
  21.         for(int i=0;i<n;i++){
  22.             while(u.size() && i+1-u.front().first>r) u.pop_front();
  23.             int k=i+1-l;
  24.             if(k>=0 && dp[old][k]!=-INF){
  25.                 LL tmp=dp[old][k]-sum[k];
  26.                 while(u.size() && tmp>u.back().second) u.pop_back();
  27.                 u.push_back(PIL(k,tmp));
  28.             }
  29.             dp[now][i+1]=dp[now][i];
  30.             pt[now][i+1]=pt[now][i];
  31.             if(u.size()){
  32.                 int at=u.front().first;
  33.                 LL tmp=u.front().second+sum[i+1];
  34.                 if(tmp>dp[now][i+1]){
  35.                     dp[now][i+1]=tmp;
  36.                     pt[now][i+1]=pt[old][at];
  37.                     pt[now][i+1].first+=i+1-at;
  38.                     pt[now][i+1].second+=pfx[i+1]-pfx[at];
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     if(!dp[m][n]) return true;
  44.     num=pt[m][n].second;
  45.     den=pt[m][n].first;
  46.     return false;
  47. }
  48.  
  49. LL floor(LL num, LL den){
  50.     if(num>=0) return num/den;
  51.     return -((-num+den-1)/den);
  52. }
  53.  
  54. int main(){
  55.     while(scanf("%d%d%d%d",&n,&m,&l,&r)==4){
  56.         for(int i=0;i<n;i++){
  57.             scanf("%d",a+i);
  58.             pfx[i+1]=pfx[i]+a[i];
  59.         }
  60.         LL num=0,den=1;
  61.         while(den && !gao(num,den));
  62.         if(!den){
  63.             puts("-1");
  64.         }else{
  65.             LL ans=floor(num*100,den);
  66.             printf("%lld.%02lld\n",ans/100,abs(ans)%100);
  67.         }
  68.     }
  69. }
  70.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lVHUQw
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!