Submission #498263

#TimeUsernameProblemLanguageResultExecution timeMemory
498263beepbeepsheep새로운 문제 (COCI19_akvizna)C++17
65 / 130
1594 ms1488 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define endl '\n' typedef pair<ll,ll> ii; typedef pair<ld,ll> ldll; const ll mod=1e9+7; const ll maxn=3e5+5; const ll inf=1e15; ll n,k; struct line{ ld m,c; ll used; line():m(0),c(0),used(0){} line(ld M, ld C, ll Used):m(M),c(C),used(Used){} ld operator()(ld x){return m*x+c;} ld POI(line l){ return (this->c-l.c)/(l.m-this->m); } bool toPop(line a, line b){ return (this->c-a.c)*(b.m-this->m)<=(this->c-b.c)*(a.m-this->m); } }; struct lch{ deque<line> dq; void upd(line a){ while (dq.size()>1){ ll s=dq.size(); if (a.toPop(dq[s-1],dq[s-2])) dq.pop_back(); else break; } dq.push_back(a); } ldll query(ld p){ while (dq.size()>1){ if (dq[0](p)<dq[1](p)) dq.pop_front(); else if (abs(dq[0](p)-dq[1](p))<=1e-16 && dq[1].used<dq[0].used) dq.pop_front(); else break; } return make_pair(dq[0](p),dq[0].used); } }*hull; //max hull ldll solve(ld cost){ hull->dq.clear(); line l; l.m=(ld)1/n,l.c=0,l.used=0; hull->upd(l); ld temp=0; for (int i=1;i<=n;i++){ ldll p = hull->query(i); temp = p.first - cost; if (i==n){ return make_pair(temp,p.second+1); } l.m=(ld)1/(n-i),l.c=temp-((ld) i/(n-i)),l.used=p.second+1; hull->upd(l); } return {0,0}; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>k; ld l=0,r=1,m; ld ans=0; hull=new lch(); ll cnt=0; while (cnt!=300){ m=(l+r)/2; ldll p=solve(m); if (p.second>k){ l=m; } else{ ans=m*p.second+p.first; r=m; } cnt++; } cout<<setprecision(10)<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...