oj.uz

Submission #97772

# Submission time Handle Problem Language Result Execution time Memory
97772 2019-02-18T12:10:16 Z alexpetrescu Akvizna (COCI19_akvizna) C++14
65 / 130
 1500 ms 69852 KB 
#include <cstdio>
#include <algorithm>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define MAXN 3000

double dp[MAXN + 1][MAXN + 1], d[MAXN + 1][MAXN + 1];
double a[MAXN + 1], b[MAXN + 1];
int dq[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) {
    u++;
    a[u] = X;
    b[u] = Y;
    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++;
}

int main() {
    int n, t;
    fscanf(fin, "%d%d", &n, &t);

    for (int i = 1; i <= t; i++) {
        st = dr = u = 0;
        for (int j = 1; j <= n; j++) {
            baga(1.0 / (n - j + 1), dp[i - 1][j - 1] - (j - 1.0) / (n - j + 1));
            scoate(j);
            dp[i][j] = a[dq[st]] * j + b[dq[st]];
        }
    }

    fprintf(fout, "%.15f\n", dp[t][n]);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message

akvizna.cpp: In function 'int main()':
akvizna.cpp:34: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 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10112 KB Output is correct
2 Correct 84 ms 37084 KB Output is correct
3 Correct 132 ms 53340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13048 KB Output is correct
2 Correct 77 ms 32508 KB Output is correct
3 Correct 97 ms 57208 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10744 KB Output is correct
2 Correct 43 ms 24796 KB Output is correct
3 Correct 101 ms 57532 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13560 KB Output is correct
2 Correct 54 ms 29816 KB Output is correct
3 Correct 97 ms 58488 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9216 KB Output is correct
2 Correct 77 ms 29560 KB Output is correct
3 Correct 87 ms 50952 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9808 KB Output is correct
2 Correct 74 ms 40620 KB Output is correct
3 Correct 95 ms 56716 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8448 KB Output is correct
2 Correct 83 ms 40700 KB Output is correct
3 Correct 106 ms 62840 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8704 KB Output is correct
2 Correct 57 ms 30584 KB Output is correct
3 Correct 106 ms 55240 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12280 KB Output is correct
2 Correct 78 ms 35236 KB Output is correct
3 Correct 99 ms 57208 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 60456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 69852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1518 ms 54444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1552 ms 52840 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1555 ms 52060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 55216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 61032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 63736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 63424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1559 ms 59388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 55080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1559 ms 62488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 53624 KB Time limit exceeded
2 Halted 0 ms 0 KB -