Submission #462289

#TimeUsernameProblemLanguageResultExecution timeMemory
462289grt새로운 문제 (COCI19_akvizna)C++17
20 / 130
915 ms600 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second #define _ ios_base::sync_with_stdio(0); cin.tie(0); //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; const int nax = 3000 + 10; int n, k; long double dp[nax]; int cnt[nax]; int main() {_ cin >> n >> k; long double low = 0.0, high = 1000.0000, mid; for(int rep = 0; rep < 30; ++rep) { mid = (low + high) / 2.0; for(int used = 0; used <= n; ++used) { dp[used] = 0; cnt[used] = 0; for(int u1 = 1; u1 <= used; ++u1) { if(dp[used] < dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid) { dp[used] = dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid; cnt[used] = cnt[used - u1] + 1; } } } if(cnt[n] <= k) { high = mid; } else { low = mid; } } mid = high; for(int used = 0; used <= n; ++used) { dp[used] = 0; cnt[used] = 0; for(int u1 = 1; u1 <= used; ++u1) { if(dp[used] < dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid) { dp[used] = dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid; cnt[used] = cnt[used - u1] + 1; } } } cout << setprecision(10); cout << fixed; cout << dp[n] + mid * cnt[n]; //<< " " << cnt[n]; }
#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...