oj.uz

Submission #222147

# Submission time Handle Problem Language Result Execution time Memory
222147 2020-04-12T08:15:12 Z VEGAnn Akvizna (COCI19_akvizna) C++14
65 / 130
 474 ms 125816 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3010;
const ll OO = 1e18;
const ld E = 1e-9;
vector<int> vc;
ld f[N][N];
int n, k;

void calc(int i, int l, int r, int opl, int opr){
    if (l > r) return;

    int j = (l + r) >> 1, opt = -1;

    for (int pr = max(j, opl); pr <= opr; pr++){
        if (f[i - 1][pr] < -E) continue;

        ld ad = f[i - 1][pr] + 1.0 - ld(j) / ld(pr);

        if (f[i][j] + E < ad) {
            f[i][j] = ad;
            opt = pr;
        }
    }

    assert(opt > -1);

    calc(i, l, j - 1, opl, opt);
    calc(i, j + 1, r, opt, opr);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> k;

    assert(n <= 3000);

    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = -1.0;

    f[0][n] = 0.0;

    for (int i = 1; i <= k; i++)
        calc(i, 0, n - 1, 0, n);

    cout << fixed << setprecision(10) << f[k][0];

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19712 KB Output is correct
2 Correct 307 ms 73976 KB Output is correct
3 Correct 414 ms 105152 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 25976 KB Output is correct
2 Correct 296 ms 64760 KB Output is correct
3 Correct 455 ms 114168 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 20992 KB Output is correct
2 Correct 216 ms 46328 KB Output is correct
3 Correct 416 ms 108536 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 26880 KB Output is correct
2 Correct 265 ms 59652 KB Output is correct
3 Correct 421 ms 114296 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 18048 KB Output is correct
2 Correct 258 ms 58744 KB Output is correct
3 Correct 384 ms 97272 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 18040 KB Output is correct
2 Correct 354 ms 81216 KB Output is correct
3 Correct 445 ms 113528 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 16512 KB Output is correct
2 Correct 331 ms 81492 KB Output is correct
3 Correct 474 ms 125816 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16896 KB Output is correct
2 Correct 244 ms 60924 KB Output is correct
3 Correct 420 ms 110584 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 24064 KB Output is correct
2 Correct 303 ms 70392 KB Output is correct
3 Correct 460 ms 114416 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -