Submission #222148

#TimeUsernameProblemLanguageResultExecution timeMemory
222148VEGAnn새로운 문제 (COCI19_akvizna)C++14
65 / 130
441 ms640 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; ld f[2][N]; int n, k, tp; void calc(int l, int r, int opl, int opr){ if (l > r) return; int j = (l + r) >> 1, opt = -1; for (int pr = max(j, opl); pr <= opr; pr++){ if (f[tp ^ 1][pr] < -E) continue; ld ad = f[tp ^ 1][pr] + 1.0 - ld(j) / ld(pr); if (f[tp][j] + E < ad) { f[tp][j] = ad; opt = pr; } } assert(opt > -1); calc(l, j - 1, opl, opt); calc(j + 1, r, opt, opr); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> k; assert(n <= 3000); for (int j = 0; j <= n; j++) f[0][j] = -1.0; f[0][n] = 0.0; for (int i = 1; i <= k; i++) { tp = (i & 1); for (int j = 0; j <= n; j++) f[tp][j] = -1.0; calc(0, n - 1, 0, n); } cout << fixed << setprecision(10) << f[k & 1][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...