Submission #955130

#TimeUsernameProblemLanguageResultExecution timeMemory
955130edogawa_somethingSparklers (JOI17_sparklers)C++17
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vii; typedef long double ld; typedef pair<ll,ll> pii; #define F first #define S second #define pb push_back #define eb emplace_back #define all(v) v.begin(),v.end() #define pow poww const ll M=1e6+10; const ll inf=2e18; const ll mod=1e9+7; ll pow(ll x,ll y){ ll res=1; x%=mod; while(y>0){ if((y&1)) res*=x,res%=mod; x*=x,x%=mod; y=(y>>1); } return res; } ll n,t,k; ld a[M]; bool chk(ld x){ vector<ld>v,vv; for(int i=k;i<n;i++){ v.pb(((a[i]-a[i-1])/ld(2))-x); } reverse(all(v)); for(int i=k-2;i>=0;i--){ vv.pb(((a[i+1]-a[i])/ld(2))-x); } reverse(all(vv)); ld cur=0; while(v.size()>0||vv.size()>0){ if(v.size()>0&&vv.size()>0){ if(v.back()<vv.back()){ cur-=v.back(); v.pop_back(); } else{ cur-=vv.back(); vv.pop_back(); } } else if(v.size()>0){ cur-=v.back(); v.pop_back(); } else{ cur-=vv.back(); vv.pop_back(); } if(cur<0){ return 0; } } return 1; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int TC=1; //cin>>TC; while(TC--){ cin>>n>>k>>t; for(int i=0;i<n;i++){ cin>>a[i]; } ld l=1,r=mod,mid; for(int i=0;i<100;i++){ mid=((l+r)/ld(2)); if(chk(mid)) r=mid; else l=mid; } ld x=ll(mid); if(x!=mid) x=x+1; ll y=x; cout<<fixed<<(y+t-1)/t<<'\n'; } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...