Submission #222144

#TimeUsernameProblemLanguageResultExecution timeMemory
222144VEGAnn새로운 문제 (COCI19_akvizna)C++14
20 / 130
1596 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; pii pr[N][N]; 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 = 0; i < k; i++) for (int j = 1; j <= n; j++){ if (f[i][j] < -E) continue; // for (int nw = j; nw > 0; nw--) { for (int nw = 0; nw <= j; nw++) { ld ad = f[i][j] + ld(nw) / ld(j); if (f[i + 1][j - nw] + E < ad) { f[i + 1][j - nw] = ad; pr[i + 1][j - nw] = MP(i, j); } } } int i = k, j = 0; while (j < n){ vc.PB(j); pii nt = pr[i][j]; i = nt.ft; j = nt.sd; } vc.PB(n); reverse(all(vc)); 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...