Submission #222170

#TimeUsernameProblemLanguageResultExecution timeMemory
222170VEGAnn새로운 문제 (COCI19_akvizna)C++14
20 / 130
1600 ms23764 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; 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.PB(nw); return; } while (sz(hull) > 1){ ld pt1 = get_cross_point(nw, hull[1]); ld pt2 = get_cross_point(hull.back(), hull[0]); if (pt2 > pt1) break; hull.pop_front(); } hull.push_front(nw); } bool check(ld extra){ fill(f, f + n + 1, MP(-1.0, 0)); f[n] = MP(0.0, 0); insert({-1.0 / ld(n), f[n].ft + 1.0, 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 + hull[l].k * ld(j) + extra, hull[l].bl + 1); } // may be this should be after update f[i][j] if (f[j].ft >= -E) insert({-1.0 / ld(j), f[j].ft + 1.0, 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(1e12); for (int it = 0; it < 100; 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); 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...