oj.uz

Submission #222610

# Submission time Handle Problem Language Result Execution time Memory
222610 2020-04-13T12:23:09 Z Vimmer Akvizna (COCI19_akvizna) C++14
130 / 130
 312 ms 5244 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 -1.0 * ld(ld(y.S - x.S) / ld(x.F - y.F));}

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

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

        if (otr.back() > crs) break;

        otr.pop_back();

        cxt.pop_back();
    }

    int j = cxt.back();

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

    cxt.pb(i);
}

void calc(ld cost)
{
    dp[n] = 0;

    kol[n] = 0;

    cxt.clear();

    otr.clear();

    cxt.pb(n);

    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) > otr[md]) r = md; else l = md + 1;
        }

        int j = cxt[l];

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

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

        add(i, cost);
    }
}

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.00000000001)
    {
        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
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 16 ms 512 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 12 ms 512 KB Output is correct

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 4976 KB Output is correct
2 Correct 262 ms 4976 KB Output is correct
3 Correct 280 ms 4976 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 4972 KB Output is correct
2 Correct 298 ms 5104 KB Output is correct
3 Correct 290 ms 5104 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4972 KB Output is correct
2 Correct 307 ms 5104 KB Output is correct
3 Correct 281 ms 5100 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 5104 KB Output is correct
2 Correct 285 ms 5104 KB Output is correct
3 Correct 273 ms 4976 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 4976 KB Output is correct
2 Correct 303 ms 5100 KB Output is correct
3 Correct 282 ms 4972 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 5244 KB Output is correct
2 Correct 278 ms 5104 KB Output is correct
3 Correct 269 ms 5104 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 5100 KB Output is correct
2 Correct 271 ms 4972 KB Output is correct
3 Correct 272 ms 4976 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 4976 KB Output is correct
2 Correct 290 ms 5100 KB Output is correct
3 Correct 285 ms 4976 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 5104 KB Output is correct
2 Correct 279 ms 5104 KB Output is correct
3 Correct 312 ms 5104 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 5244 KB Output is correct
2 Correct 288 ms 4976 KB Output is correct
3 Correct 291 ms 5104 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 5104 KB Output is correct
2 Correct 298 ms 5080 KB Output is correct
3 Correct 285 ms 5104 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 5104 KB Output is correct
2 Correct 296 ms 5100 KB Output is correct
3 Correct 298 ms 5104 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 5100 KB Output is correct
2 Correct 294 ms 5104 KB Output is correct
3 Correct 285 ms 5104 KB Output is correct