Submission #102971

#TimeUsernameProblemLanguageResultExecution timeMemory
102971mraron새로운 문제 (COCI19_akvizna)C++14
65 / 130
1562 ms11512 KiB
#include<iostream> #include<vector> #include<map> #include<set> #include<cassert> #include<cassert> #include<unordered_map> #include<unordered_set> #include<functional> #include<queue> #include<stack> #include<cstring> #include<algorithm> #include<cmath> #include<sstream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<numeric> using namespace std; #define all(x) (x).begin(), (x).end() #define pb push_back #define xx first #define yy second #define sz(x) (int)(x).size() #define gc getchar #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define mp make_pair #ifndef ONLINE_JUDGE # define LOG(x) (cerr << #x << " = " << (x) << endl) #else # define LOG(x) ((void)0) #endif typedef long long ll; typedef unsigned long long ull; typedef long double ld; const double PI=3.1415926535897932384626433832795; const ll INF = 1LL<<62; const ll MINF = -1LL<<62; template<typename T> T getint() { T val=0; char c; bool neg=false; while((c=gc()) && !(c>='0' && c<='9')) { neg|=c=='-'; } do { val=(val*10)+c-'0'; } while((c=gc()) && (c>='0' && c<='9')); return val*(neg?-1:1); } // // SQRT time convex hull trick // struct line { ld xx; ld yy; int cnt; int par; bool operator<(const line& masik) const { return cnt<masik.cnt; } }; struct sqrt_CHT { int mn; int blksz; vector<line> hull, reserve; sqrt_CHT(bool min_, int blksz_) { mn=min_?1:-1; blksz=blksz_; } // // Checks wheter b is optimal if a<b<c holds // Complexity: O(1) // bool optimal(line& a, line& b, line& c) { return double(b.yy-a.yy)*double(c.xx-b.xx)>double(b.yy-c.yy)*double(a.xx-b.xx); } // // Inserts linear function into the hull // Complexity: O(1) if reserve is not full else O(sz(hull) log sz(hull) + blksz) // void insert(line a) { a.xx*=mn;a.yy*=mn; reserve.pb(a); if(sz(reserve)>=blksz) { for(auto i:reserve) { hull.pb(i); } reserve.resize(0); sort(all(hull), [](const line& a, const line& b) -> bool { if(a.xx==b.xx) { return a.yy>b.yy; } return a.xx>b.xx; }); vector<line> nhull; for(auto i:hull) { nhull.pb(i); while((sz(nhull)>=2 && nhull[sz(nhull)-1].xx==nhull[sz(nhull)-2].xx) || (sz(nhull)>=3 && !optimal(nhull[sz(nhull)-3], nhull[sz(nhull)-2], nhull[sz(nhull)-1]))) { line tmp=nhull.back(); nhull.pop_back(); nhull.pop_back(); nhull.pb(tmp); } } hull.swap(nhull); } } // // Gets the optimal (minimal or maximal) value of inserted function at a given x point // Complexity: O(log(sz(hull)) + blksz) // pair<ld, line> get(ld x) { pair<ld,line> ans; ans.xx=100000000.0; for(auto i:reserve) { pair<ld,line> akt=mp(ld(i.xx*x+i.yy), i); ans=min(ans, akt); } if(hull.empty()) { ans.xx*=mn; return ans; } int L=0, R=sz(hull)-1; while(L<R) { int mid=(L+R+1)/2; ld val1=hull[mid-1].xx*x+hull[mid-1].yy, val2=hull[mid].xx*x+hull[mid].yy; if(val1<val2) { R=mid-1; }else { L=mid; } } ans=min(ans, mp(hull[L].xx*x+hull[L].yy, hull[L])); ans.xx*=mn; return ans; } private: }; double dp[100001]; int cnt[100001]; int par[100001]; int main() { IO; int n,k,it=0; cin>>n>>k; double L=0, R=2; while(1) { double mid=(L+R)/2; dp[0]=0; cnt[0]=0; sqrt_CHT cht(false, 300); cht.insert({double(1)/double(n),0,0, 0}); for(int i=1;i<=n;++i) { pair<ld, line> val=cht.get(i); dp[i]=val.xx-mid; cnt[i]=val.yy.cnt+1; par[i]=val.yy.par; if(i<n) { cht.insert({double(1)/double(n-i),dp[i]-double(i)/double(n-i),cnt[i], i}); // cerr<<double(1)/double(n-i)<<" "<<dp[i]-double(i)/double(n-i)<<"\n"; } /*for(int j=1;i+j<=n;j++) { double akt=dp[i]+double(j)/double(n-i)-mid; if(dp[i+j]<akt) { dp[i+j]=akt; cnt[i+j]=cnt[i]+1; } }*/ } //cerr<<mid<<" "<<cnt[n]<<"\n"; if(cnt[n]<=k) { R=mid; }else { L=mid; } it++; if(it>=40 && cnt[n]==k) break ; } cout<<fixed<<setprecision(9); cout<<dp[n]+L*cnt[n]<<"\n"; /* int akt=n; while(akt>0) { cerr<<akt-par[akt]<<"/"<<n-par[akt]<<"\n"; akt=par[akt]; }*/ return 0; } /* double dp[3001][3001]; int main() { IO; int n,k; cin>>n>>k; dp[n][0]=0.0; for(int i=1;i<=k;++i) { for(int j=0;j<=n;++j) { for(int l=0;l<=n/i && j+l<=n;l++) { dp[j][i]=max(dp[j][i], dp[j+l][i-1]+(l>0?(double)l/(double)(j+l):0)); } } } cout<<fixed<<setprecision(10); cout<<dp[0][k]<<"\n"; 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...