oj.uz

Submission #222461

# Submission time Handle Problem Language Result Execution time Memory
222461 2020-04-13T07:50:45 Z Vimmer Akvizna (COCI19_akvizna) C++14
0 / 130
 1500 ms 11884 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;


int kol[N], n, k;

ld dp[N];

vector <int> cxt;

vector <ld> otr;

ld cross(pair <ld, ld> x, pair <ld, ld> y) {return ld(ld(y.S - y.F) / ld(x.F - y.F));}

void add(int i)
{
    while (sz(cxt) > 1)
    {
        int j = cxt[sz(cxt) - 2], u = cxt.back();

        ld crs1 = cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)});

        ld crs2 = cross({dp[u], ld(1) / ld(u)}, {dp[j], ld(1) / ld(j)});

        if (crs2 > crs1) break;

        otr.pop_back();

        cxt.pop_back();
    }

    int j = cxt.back();

    otr.pb(cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)}));

    cout << cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)}) << endl;

    cxt.pb(i);
}
void calc(ld cost)
{
    dp[n] = 0;

    kol[n] = 0;

    cxt.clear();

    otr.clear();

    cxt.pb(n);

    otr.pb(1e9);

    for (int i = n - 1; i >= 0; i--)
    {
        int l = 0, r = sz(cxt) - 1;

        while (l < r)
        {
            int md = (r + l) >> 1;

            if (ld(i) + cost <= otr[md]) r = md; else l = md + 1;
        }

        int j = cxt[l];

        kol[i] = kol[j] + 1;

        dp[i] = dp[j] + cost + ld(j - i) * (ld(1) / ld(j));

        add(i);
    }
}

int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    cout << setprecision(9) << fixed;

    ld l = -1, r = 0;

    while (r - l > 0.0000000000001)
    {
        ld md = (r + l) / 2.0;

        calc(md);

        if (kol[0] <= k) l = md; else r = md;
    }

    calc(l);

    cout << ld(dp[0] - l * ld(kol[0]));
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 361 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 361 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 2292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 323 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 346 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 365 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 11348 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 1587 ms 11188 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 1584 ms 11492 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 1593 ms 11768 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 1584 ms 10984 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 1582 ms 11884 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 1590 ms 11564 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 1592 ms 11308 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 1583 ms 11348 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 1599 ms 11312 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 1599 ms 11436 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 1587 ms 11496 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 1588 ms 11344 KB Time limit exceeded
2 Halted 0 ms 0 KB -