답안 #222187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222187	2020-04-12T09:52:18 Z	Vimmer	Akvizna (COCI19_akvizna)	C++14	65 / 130	1200 ms	1152 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;


ld last[10001], now[10001];

vector <pair <ld, ld> > otr;

vector <int> conv;

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

ld calc(int a, int b)
{
    ld x = a;

    ld y = b;

    ld sm = 0;

    if (y != 0) sm = x / y;

    return last[b] + sm;
}

int main()
{

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

    int n, k;

    cin >> n >> k;

    cout << setprecision(9) << fixed;

    if (k >= n)
    {
        ld ans = 0;

        for (int i = 1; i <= n; i++) ans += ld(i) / ld(n);

        cout << ans << endl;

        exit(0);
    }

    for (int i = 0; i <= n; i++) {last[i] = 0; now[i] = 0;}

    for (int j = 0; j < k; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            int l = i, r = n;

            while (l + 10 < r)
            {
                int mdl = l + (r - l) / 3;

                int mdr = r - (r - l) / 3;

                if (calc(mdl - i, mdl) > calc(mdr - i, mdr)) r = mdr; else l = mdl;
            }

            for (int j = l; j <= r; j++) now[i] = max(now[i], calc(j - i, j));

        }

        for (int i = 0; i <= n; i++) {last[i] = now[i]; now[i] = 0;}

    }

    cout << last[0];
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	256 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	384 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	196 ms	504 KB	Output is correct
2	Correct	813 ms	504 KB	Output is correct
3	Correct	1059 ms	504 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	249 ms	384 KB	Output is correct
2	Correct	678 ms	504 KB	Output is correct
3	Correct	1116 ms	504 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	230 ms	504 KB	Output is correct
2	Correct	454 ms	384 KB	Output is correct
3	Correct	1087 ms	384 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	504 KB	Output is correct
2	Correct	651 ms	488 KB	Output is correct
3	Correct	1150 ms	632 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	190 ms	384 KB	Output is correct
2	Correct	625 ms	508 KB	Output is correct
3	Correct	928 ms	504 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	188 ms	468 KB	Output is correct
2	Correct	889 ms	504 KB	Output is correct
3	Correct	1173 ms	504 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	168 ms	384 KB	Output is correct
2	Correct	892 ms	520 KB	Output is correct
3	Correct	1200 ms	384 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	156 ms	384 KB	Output is correct
2	Correct	603 ms	492 KB	Output is correct
3	Correct	1084 ms	504 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	266 ms	504 KB	Output is correct
2	Correct	765 ms	512 KB	Output is correct
3	Correct	1175 ms	632 KB	Output is correct

Subtask #14
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #22
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #23
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #24
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #25
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #26
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

답안 #222187

Compilation message