oj.uz

Submission #222144

# Submission time Handle Problem Language Result Execution time Memory
222144 2020-04-12T08:03:08 Z VEGAnn Akvizna (COCI19_akvizna) C++14
20 / 130
 1500 ms 262144 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;
pii pr[N][N];

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

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

    cin >> n >> k;

    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 = 0; i < k; i++)
    for (int j = 1; j <= n; j++){
        if (f[i][j] < -E) continue;

//        for (int nw = j; nw > 0; nw--) {
        for (int nw = 0; nw <= j; nw++) {
            ld ad = f[i][j] + ld(nw) / ld(j);

            if (f[i + 1][j - nw] + E < ad) {
                f[i + 1][j - nw] = ad;
                pr[i + 1][j - nw] = MP(i, j);
            }
        }
    }

    int i = k, j = 0;

    while (j < n){
        vc.PB(j);
        pii nt = pr[i][j];
        i = nt.ft;
        j = nt.sd;
    }
    vc.PB(n);
    reverse(all(vc));

    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 768 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 6 ms 1152 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 6 ms 768 KB Output is correct
3 Correct 6 ms 896 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 813 ms 262144 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 801 ms 262144 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 792 ms 262144 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 807 ms 262144 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 795 ms 262144 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 843 ms 262144 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 835 ms 262144 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 780 ms 262144 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 834 ms 262144 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 848 ms 262144 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 844 ms 262144 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 851 ms 262144 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 847 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -