Submission #462307

#TimeUsernameProblemLanguageResultExecution timeMemory
462307grt새로운 문제 (COCI19_akvizna)C++17
65 / 130
243 ms3520 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 = 100 * 1000 + 10; int n, k; long double dp[nax]; int cnt[nax]; struct Line { long double a, b; int id; long double intersect(Line &he) { return (b - he.b) / (he.a - a); } long double eval(int x) { return a * x + b; } }; deque<Line>lines; int main() {_ cin >> n >> k; long double low = 0.0, high = 1.0000, mid; for(int rep = 0; rep < 30; ++rep) { mid = (low + high) / 2.0; while((int)lines.size() > 0) lines.pop_back(); for(int used = 0; used <= n; ++used) { dp[used] = 0; cnt[used] = 0; while((int)lines.size() > 1 && lines[0].eval(used - n) <= lines[1].eval(used - n)) { lines.pop_front(); } long double res = 0.0; if((int)lines.size() > 0) { res = lines[0].eval(used - n) - mid; cnt[used] = cnt[lines[0].id] + 1; } dp[used] = max(dp[used], res); if(used < n) { Line l = {(long double)1/(n - used), dp[used] + 1.0, used}; while((int)lines.size() > 1 && lines[(int)lines.size() - 2].intersect(l) <= lines[(int)lines.size() - 2].intersect(lines.back())) { lines.pop_back(); } lines.push_back(l); } } if(cnt[n] <= k) { high = mid; } else { low = mid; } } mid = high; while((int)lines.size() > 0) lines.pop_back(); for(int used = 0; used <= n; ++used) { dp[used] = 0; cnt[used] = 0; while((int)lines.size() > 1 && lines[0].eval(used - n) <= lines[1].eval(used - n)) { lines.pop_front(); } long double res = 0.0; if((int)lines.size() > 0) { res = lines[0].eval(used - n) - mid; cnt[used] = cnt[lines[0].id] + 1; } dp[used] = max(dp[used], res); if(used < n) { Line l = {(long double)1/(n - used), dp[used] + 1.0, used}; while((int)lines.size() > 1 && lines[(int)lines.size() - 2].intersect(l) <= lines[(int)lines.size() - 2].intersect(lines.back())) { lines.pop_back(); } lines.push_back(l); } } cout << setprecision(10); cout << fixed; cout << dp[n] + mid * k; }
#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...