# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
97790 | alexpetrescu | 새로운 문제 (COCI19_akvizna) | C++14 | 118 ms | 4344 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout
#define MAXN 100000
struct myc {
double x;
int y;
} dp[MAXN + 1];
double a[MAXN + 1], b[MAXN + 1];
int n, dq[MAXN + 1], cati[MAXN + 1], u, st, dr;
inline double intersect(int p, int q) {
return (b[q] - b[p]) / (a[p] - a[q]);
}
inline void baga(double X, double Y, int Z) {
u++;
a[u] = X;
b[u] = Y;
cati[u] = Z;
while (st < dr && (b[dq[dr - 1]] <= b[u] || (st < dr - 1 && intersect(dq[dr - 2], dq[dr - 1]) > intersect(dq[dr - 2], u))))
dr--;
dq[dr++] = u;
}
inline void scoate(int p) {
while (st < dr - 1 && a[dq[st]] * p + b[dq[st]] < a[dq[st + 1]] * p + b[dq[st + 1]])
st++;
}
inline void calc(double lamda) {
st = dr = u = 0;
for (int j = 1; j <= n; j++) {
baga(1.0 / (n - j + 1), dp[j - 1].x - (j - 1.0) / (n - j + 1), dp[j - 1].y);
scoate(j);
dp[j] = {a[dq[st]] * j + b[dq[st]] - lamda, cati[dq[st]] + 1};
}
}
int main() {
int t;
fscanf(fin, "%d%d", &n, &t);
for (int i = 1; i <= t; i++) {
st = dr = u = 0;
}
double lamda = 0, ans = 0;
for (double pas = 13; pas > 0.0000000000001; pas /= 2) {
calc(lamda + pas);
if (dp[n].y >= t) {
lamda += pas;
ans = dp[n].x + t * lamda;
}
}
fprintf(fout, "%.15f\n", ans);
fclose(fin);
fclose(fout);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |