oj.uz

Submission #97790

# Submission time Handle Problem Language Result Execution time Memory
97790 2019-02-18T13:42:18 Z alexpetrescu Akvizna (COCI19_akvizna) C++14
130 / 130
 118 ms 4344 KB 
#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

akvizna.cpp: In function 'int main()':
akvizna.cpp:47:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d", &n, &t);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4092 KB Output is correct
2 Correct 73 ms 4004 KB Output is correct
3 Correct 68 ms 3836 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4028 KB Output is correct
2 Correct 65 ms 4188 KB Output is correct
3 Correct 55 ms 4100 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3992 KB Output is correct
2 Correct 61 ms 4252 KB Output is correct
3 Correct 68 ms 4216 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4088 KB Output is correct
2 Correct 118 ms 4088 KB Output is correct
3 Correct 59 ms 3968 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3960 KB Output is correct
2 Correct 61 ms 4216 KB Output is correct
3 Correct 53 ms 4044 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4252 KB Output is correct
2 Correct 58 ms 3976 KB Output is correct
3 Correct 54 ms 4056 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4088 KB Output is correct
2 Correct 54 ms 3920 KB Output is correct
3 Correct 54 ms 3976 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3980 KB Output is correct
2 Correct 95 ms 4216 KB Output is correct
3 Correct 80 ms 3960 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4232 KB Output is correct
2 Correct 65 ms 4164 KB Output is correct
3 Correct 57 ms 4220 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4216 KB Output is correct
2 Correct 62 ms 3960 KB Output is correct
3 Correct 57 ms 4216 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4244 KB Output is correct
2 Correct 80 ms 4248 KB Output is correct
3 Correct 70 ms 4216 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4224 KB Output is correct
2 Correct 63 ms 4260 KB Output is correct
3 Correct 78 ms 4344 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4224 KB Output is correct
2 Correct 62 ms 4256 KB Output is correct
3 Correct 63 ms 4316 KB Output is correct