답안 #223047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223047	2020-04-14T14:54:54 Z	Vimmer	Akvizna (COCI19_akvizna)	C++14	130 / 130	307 ms	5152 KB

akvizna

#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(10) << 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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 #7
5.0 / 5.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	512 KB	Output is correct
2	Correct	12 ms	640 KB	Output is correct
3	Correct	12 ms	512 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	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 #10
5.0 / 5.0

#	결과	실행 시간	메모리	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 #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	512 KB	Output is correct
2	Correct	15 ms	512 KB	Output is correct
3	Correct	12 ms	512 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	512 KB	Output is correct
2	Correct	13 ms	520 KB	Output is correct
3	Correct	13 ms	512 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	264 ms	5104 KB	Output is correct
2	Correct	292 ms	4976 KB	Output is correct
3	Correct	253 ms	4976 KB	Output is correct

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	276 ms	4976 KB	Output is correct
2	Correct	301 ms	5104 KB	Output is correct
3	Correct	280 ms	4976 KB	Output is correct

Subtask #16
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	274 ms	4976 KB	Output is correct
2	Correct	300 ms	5104 KB	Output is correct
3	Correct	292 ms	5100 KB	Output is correct

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	291 ms	5104 KB	Output is correct
2	Correct	276 ms	5104 KB	Output is correct
3	Correct	280 ms	4976 KB	Output is correct

Subtask #18
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	257 ms	4976 KB	Output is correct
2	Correct	296 ms	5100 KB	Output is correct
3	Correct	264 ms	4976 KB	Output is correct

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	307 ms	5104 KB	Output is correct
2	Correct	267 ms	4972 KB	Output is correct
3	Correct	262 ms	4972 KB	Output is correct

Subtask #20
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	284 ms	5104 KB	Output is correct
2	Correct	277 ms	4976 KB	Output is correct
3	Correct	279 ms	4976 KB	Output is correct

Subtask #21
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	5100 KB	Output is correct
2	Correct	298 ms	5104 KB	Output is correct
3	Correct	274 ms	5104 KB	Output is correct

Subtask #22
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	285 ms	5100 KB	Output is correct
2	Correct	298 ms	5104 KB	Output is correct
3	Correct	299 ms	5104 KB	Output is correct

Subtask #23
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	280 ms	5100 KB	Output is correct
2	Correct	284 ms	5104 KB	Output is correct
3	Correct	297 ms	5104 KB	Output is correct

Subtask #24
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	304 ms	5152 KB	Output is correct
2	Correct	298 ms	5100 KB	Output is correct
3	Correct	298 ms	5104 KB	Output is correct

Subtask #25
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	277 ms	5104 KB	Output is correct
2	Correct	297 ms	5100 KB	Output is correct
3	Correct	303 ms	5100 KB	Output is correct

Subtask #26
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	301 ms	5104 KB	Output is correct
2	Correct	280 ms	5100 KB	Output is correct
3	Correct	296 ms	5104 KB	Output is correct

답안 #223047

Compilation message