Submission #222159

#TimeUsernameProblemLanguageResultExecution timeMemory
222159VEGAnn새로운 문제 (COCI19_akvizna)C++14
0 / 130
1606 ms262144 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 = 3010; const ll OO = 1e18; const ld E = 1e-9; vector<int> vc; ld f[N][N]; int n, k; struct line{ ld k, b; line(): k(0.0), b(0.0) {} line(ld _k, ld _b): k(_k), b(_b) {} }; 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); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> k; for (int i = 0; i <= k; i++) for (int j = 0; j <= n; j++) f[i][j] = -1.0; f[0][n] = 0.0; for (int i = 1; i <= k; i++) { hull.clear(); if (f[i - 1][n] >= -E) insert({-1.0 / ld(n), f[i - 1][n] + 1.0}); for (int j = n - 1; j >= 0; j--){ // may be this should be after update f[i][j] if (f[i - 1][j] >= -E) insert({-1.0 / ld(j), f[i - 1][j] + 1.0}); 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[i][j] = hull[l].b + hull[l].k * ld(j); } } } cout << fixed << setprecision(10) << f[k][0]; 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...