Submission #222157

#TimeUsernameProblemLanguageResultExecution timeMemory
222157NONAME새로운 문제 (COCI19_akvizna)C++17
65 / 130
1596 ms3456 KiB
#include <bits/stdc++.h> #include <time.h> //#include <random> #define sz(x) int(x.size()) #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #define N 100500 #define oo ll(1e16) #define pii pair <int, int> #define pll pair <ll, ll> #define ft first #define sd second #define pb push_back #define ppb pop_back #define el '\n' #define elf endl #define base ll(1e9 + 7) #define re return #define nins 4294967295 using namespace std; typedef long long ll; typedef long double ld; //mt19937 rnd(0); int n, k; ld f[2][N]; void solve(int cr, int l, int r, int opl, int opr) { if (l > r) return; int md = (l + r) >> 1; int op = -1; for (int i = opl; i <= min(md, opr); i++) { if (f[1 ^ cr][i] == -1) continue; if (f[cr ^ 1][i] + ld(md - i) / ld(md) > f[cr][md]) { f[cr][md] = f[cr ^ 1][i] + ld(md - i) / ld(md); op = i; } } solve(cr, l, md - 1, opl, op); solve(cr, md + 1, r, op, opr); } void solve() { cin >> n >> k; for (int i = 0; i <= n; i++) f[1][i] = 1; for (int i = 2; i <= k; i++) { for (int j = 0; j <= n; j++) f[i & 1][j] = -1; solve(i & 1, 1, n, 1, n); } cout.precision(10); cout << fixed; cout << f[k & 1][n]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef _LOCAL in("input.txt"); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { cout << "Test #" << i << elf; clock_t start_time = clock(); solve(); cerr.precision(4); cerr << fixed; cerr << elf; cerr << "Time :: " << ld(clock() - start_time) / CLOCKS_PER_SEC << elf; cout << elf; } #else int t = 1; // cin >> t; while (t--) { solve(); cout << el; } #endif }
#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...