Boxes
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,double> pid; const int inf=0x3f3f3f3f; const double eps=1e-8; const int N=100010; int n; long double c; long double w[N]; long double qpow(long double a,long long b){ long double res=1; while(b){ if(b&1) res=res*a; a=a*a; b>>=1; } return res; } int main(){ scanf("%d%Lf",&n,&c); long double ans=0.0; for(int i=1;i<=n;i++){ scanf("%Lf",&w[i]); ans=ans+(long double)w[i]; } sort(w+1,w+n+1); n--; long double _ans=c; ll cnt=2; for(int i=n;i>=max(n-100,1);i--){ _ans=_ans+(1.0-2.0/(long double)qpow(2,cnt))*w[i]; cnt++; } for(int i=1;i<=max(n-100,1)-1;i++){ _ans=_ans+1.0*w[i]; } if(_ans-ans>eps) _ans=ans; printf("%.16Lf",_ans); }
King of Range
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,double> pid; const int inf=0x3f3f3f3f; const double eps=1e-8; const int N=100010; int n,m; int k; int a[N]; int q1[N],q2[N]; int hh1,hh2; int tt1,tt2; ll ans; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(m--){ scanf("%d",&k); hh1=hh2=0; tt1=tt2=-1; ans=1ll*n*(n+1)/2; for(int i=1,j=1;i<=n;i++){ while(hh1<=tt1&&a[q1[tt1]]<a[i]) tt1--; while(hh2<=tt2&&a[q2[tt2]]>a[i]) tt2--; q1[++tt1]=i; q2[++tt2]=i; while(a[q1[hh1]]-a[q2[hh2]]>k){ j++; if(q1[hh1]<j) hh1++; if(q2[hh2]<j) hh2++; } ans-=1ll*(i-j+2)*(i-j+1)/2; ans+=1ll*(i-j+1)*(i-j)/2; } printf("%lld\n",ans); } }