oj.uz

Submission #410570

# Submission time Handle Problem Language Result Execution time Memory
410570 2021-05-23T02:42:29 Z koioi.org-namnamseo Akvizna (COCI19_akvizna) C++17
125 / 130
 41 ms 1840 KB 
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = int(1e5) + 10;

int r, n;

double dp[maxn];
int usg[maxn];
int uc[maxn];
int f(double c) {
	int j = 1;
	for (int i=1; i<=n; ++i) {
		dp[i] = 0;
		double jc = double(j)/i + dp[i-j] - c;
		while (j+1 <= i) {
			double tmp = double(j+1)/i + dp[i-j-1] - c;
			if (jc < tmp) {
				jc = tmp;
				++j;
			} else break;
		}
		dp[i] = jc;
		usg[i] = i-j;
		uc[i] = uc[i-j] + 1;
	}
	return uc[n];
}

int main()
{
	cin >> n >> r;

	double cl = 0, cr = 10;
	for (int i=0; i<50; ++i) {
		double mid = (cl+cr)/2;
		if (r < f(mid)) cl = mid;
		else cr = mid;
	}

	f(cl);
	static char out[256];
	sprintf(out, "%.10f", dp[n]+r*cl);
	cout << out << '\n';

	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1740 KB Output is correct
2 Correct 37 ms 1780 KB Output is correct
3 Correct 35 ms 1612 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1740 KB Output is correct
2 Correct 36 ms 1740 KB Output is correct
3 Correct 37 ms 1784 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1740 KB Output is correct
2 Correct 37 ms 1836 KB Output is correct
3 Correct 40 ms 1740 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1740 KB Output is correct
2 Correct 37 ms 1804 KB Output is correct
3 Correct 35 ms 1740 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1740 KB Output is correct
2 Correct 37 ms 1740 KB Output is correct
3 Correct 36 ms 1740 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1740 KB Output is correct
2 Correct 37 ms 1740 KB Output is correct
3 Correct 36 ms 1740 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1740 KB Output is correct
2 Correct 35 ms 1728 KB Output is correct
3 Correct 34 ms 1740 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1740 KB Output is correct
2 Correct 37 ms 1740 KB Output is correct
3 Correct 34 ms 1740 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1740 KB Output is correct
2 Correct 37 ms 1800 KB Output is correct
3 Correct 38 ms 1836 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1740 KB Output is correct
2 Correct 36 ms 1772 KB Output is correct
3 Correct 37 ms 1740 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1740 KB Output is correct
2 Correct 37 ms 1836 KB Output is correct
3 Correct 38 ms 1740 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1740 KB Output is correct
2 Correct 38 ms 1740 KB Output is correct
3 Correct 37 ms 1740 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1840 KB Output is correct
2 Correct 39 ms 1740 KB Output is correct
3 Correct 41 ms 1740 KB Output is correct