Submission #222215

#TimeUsernameProblemLanguageResultExecution timeMemory
222215VEGAnn새로운 문제 (COCI19_akvizna)C++14
20 / 130
1184 ms17196 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define pii pair<int,int> #define ft first #define sd second #define MP make_pair #define all(x) x.begin(),x.end() #define PB push_back using namespace std; typedef long long ll; typedef long double ld; const int N = 100100; const ll OO = 1e18; const ld E = 1e-9; const ld CNST = 1; vector<int> vc; pair<ld, int> f[N]; int n, k; struct line{ ld k, b; int bl; line(): k(0.0), b(0.0), bl(0) {} line(ld _k, ld _b, int i): k(_k), b(_b), bl(i) {} }; deque<line> hull; ld get_cross_point(line fi, line se){ return (fi.b - se.b) / (se.k - fi.k); } void insert(line nw){ if (sz(hull) == 0){ hull.push_front(nw); return; } while (sz(hull) > 1){ ld pt1 = get_cross_point(nw, hull[1]); ld pt2 = get_cross_point(hull[1], hull[0]); if (pt2 > pt1) break; hull.pop_front(); } hull.push_front(nw); } bool check(ld extra){ hull.clear(); f[n] = MP(0.0, 0); insert({-1.0 / ld(n), f[n].ft, 0}); for (int j = n - 1; j >= 0; j--){ if (sz(hull)) { int l = 0, r = sz(hull) - 1; while (l < r) { int md = (l + r + 1) >> 1; assert(md > 0); if (get_cross_point(hull[md], hull[md - 1]) + E < j) l = md; else r = md - 1; } f[j] = MP(hull[l].b + 1.0 + hull[l].k * ld(j) + extra, hull[l].bl + 1); } insert({-1.0 / ld(j), f[j].ft, f[j].sd}); } return (f[0].sd <= k); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> k; ld l = 0, r = ld(1e9); for (int it = 0; it < 50; it++){ ld md = (l + r) / 2.0; if (check(-md)) r = md; else l = md; if (f[0].sd == k){ l = md; break; } } check(-l); assert(f[0].sd == k); cout << fixed << setprecision(10) << (f[0].ft + l * ld(k) * CNST) / CNST; 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...