Submission #873911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873911	2023-11-16T02:42:12 Z	noiaint	Akvizna (COCI19_akvizna)	C++17	130 / 130	196 ms	3984 KB

akvizna

#include <bits/stdc++.h>
#define int long long
#define double long double
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll
 
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}
 
const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;
 
template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
 
template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
 
template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}
 
const double eps = 1e-10;
 
int n, k;
int cnt[N];
double f[N];
 
double F(int j, int k) {
    return (f[j] - f[k]) / (j - k);
}
 
bool ok(double mid) {
    deque<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; ++i) {
        while (q.size() >= 2 && F(q[0], q[1]) > 1.0 / i) q.pop_front();
        int j = q.front();
        f[i] = f[j] + (double) (i - j) / i - mid;
        cnt[i] = cnt[j] + 1;
        while (q.size() >= 2 && F(q[q.size() - 2], q[q.size() - 1]) < F(q[q.size() - 1], i)) q.pop_back();
        q.push_back(i);
    }
    return cnt[n] >= k;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
    double l = 0, r = 1e9, mid;
    while (r - l >= eps) {
        mid = (l + r) / 2;
        if (ok(mid)) l = mid; else r = mid;
    }
 
    cout.precision(12);
    cout << fixed;
    cout << f[n] + (double) mid * k;
 
    return 0;
}
 
/*
 
*/

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	464 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	600 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	344 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	344 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	5 ms	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	552 KB	Output is correct
2	Correct	4 ms	348 KB	Output is correct
3	Correct	4 ms	548 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	348 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	344 KB	Output is correct
2	Correct	5 ms	464 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	348 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	5 ms	348 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	348 KB	Output is correct
2	Correct	5 ms	344 KB	Output is correct
3	Correct	4 ms	468 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	348 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	348 KB	Output is correct
2	Correct	5 ms	348 KB	Output is correct
3	Correct	4 ms	348 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	3768 KB	Output is correct
2	Correct	156 ms	3680 KB	Output is correct
3	Correct	152 ms	3688 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	3676 KB	Output is correct
2	Correct	154 ms	3724 KB	Output is correct
3	Correct	155 ms	3824 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	3676 KB	Output is correct
2	Correct	157 ms	3756 KB	Output is correct
3	Correct	156 ms	3760 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	3760 KB	Output is correct
2	Correct	155 ms	3840 KB	Output is correct
3	Correct	145 ms	3680 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	3680 KB	Output is correct
2	Correct	158 ms	3756 KB	Output is correct
3	Correct	146 ms	3740 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	3752 KB	Output is correct
2	Correct	150 ms	3736 KB	Output is correct
3	Correct	153 ms	3692 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	3752 KB	Output is correct
2	Correct	151 ms	3668 KB	Output is correct
3	Correct	143 ms	3664 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	3912 KB	Output is correct
2	Correct	156 ms	3760 KB	Output is correct
3	Correct	141 ms	3664 KB	Output is correct

Subtask #22
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	3760 KB	Output is correct
2	Correct	158 ms	3984 KB	Output is correct
3	Correct	156 ms	3856 KB	Output is correct

Subtask #23
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	3752 KB	Output is correct
2	Correct	150 ms	3736 KB	Output is correct
3	Correct	154 ms	3764 KB	Output is correct

Subtask #24
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	3764 KB	Output is correct
2	Correct	158 ms	3756 KB	Output is correct
3	Correct	164 ms	3984 KB	Output is correct

Subtask #25
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	3752 KB	Output is correct
2	Correct	163 ms	3764 KB	Output is correct
3	Correct	182 ms	3700 KB	Output is correct

Subtask #26
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	3700 KB	Output is correct
2	Correct	163 ms	3704 KB	Output is correct
3	Correct	196 ms	3704 KB	Output is correct

Submission #873911

Compilation message