yicongli

Gym 101848G

Jan 23rd, 2021
1,096
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8. #define db double
  9.  
  10. template<typename T>
  11. inline void read(T&x){
  12.     x=0;T k=1;char gc;
  13.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  14.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  15. }
  16.  
  17. const int N=5e5+7;
  18.  
  19. int t[N];
  20. int y[N];
  21. db f[N];
  22. db tag[N];
  23.  
  24. int main(){
  25.     // freopen(".in","r",stdin);
  26.     // freopen(".out","w",stdout);
  27.     int n,h;r(n),r(h);
  28.     for(int i=1;i<=n;++i){
  29.         r(t[i]),r(y[i]);
  30.         y[i]+=1e5;
  31.     }
  32.     y[0]=1e5;
  33.     for(int i=1;i<=n;++i){
  34.         int l=min(y[i-1],y[i]);
  35.         int r=max(y[i-1],y[i]);
  36.         if(l==r){
  37.             tag[l]+=(t[i]-t[i-1]);
  38.             continue;
  39.         }
  40.         db w=(t[i]-t[i-1])/(db)(r-l);
  41.         f[l+1]+=w;
  42.         f[r+1]-=w;
  43.     }
  44.     for(int i=1;i<=2e5+h;++i)f[i]+=f[i-1];
  45.     db sum=0;
  46.     for(int i=0;i<=h;++i){
  47.         sum+=f[i]+tag[i];
  48.     }
  49.     db ans=sum;
  50.     for(int i=1;i<=2e5;++i){
  51.         // printf("l=%d, r=%d, sum=%.8lf\n",i,i+h,f[i+h]-f[i]);
  52.         sum-=f[i]+tag[i-1];
  53.         sum+=f[i+h]+tag[i+h];
  54.         ans=max(ans,sum);
  55.     }
  56.     printf("%.8lf\n",ans);
  57.     return 0;
  58. }
  59. /*
  60. 3 2
  61. 50 0
  62. 75 2
  63. 100 2
  64. */
RAW Paste Data