oj.uz

Submission #410571

# Submission time Handle Problem Language Result Execution time Memory
410571 2021-05-23T02:48:24 Z koioi.org-namnamseo Akvizna (COCI19_akvizna) C++17
130 / 130
 166 ms 1868 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;
		j -= 10;
		if (j <= 0) j = 1;
		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 = 2;
	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
5.0 / 5.0

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

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 5 ms 460 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1724 KB Output is correct
2 Correct 121 ms 1772 KB Output is correct
3 Correct 102 ms 1692 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 1756 KB Output is correct
2 Correct 116 ms 1740 KB Output is correct
3 Correct 108 ms 1740 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 1740 KB Output is correct
2 Correct 129 ms 1832 KB Output is correct
3 Correct 118 ms 1740 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1784 KB Output is correct
2 Correct 119 ms 1740 KB Output is correct
3 Correct 107 ms 1744 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1740 KB Output is correct
2 Correct 121 ms 1868 KB Output is correct
3 Correct 108 ms 1740 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 1836 KB Output is correct
2 Correct 122 ms 1772 KB Output is correct
3 Correct 107 ms 1752 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1800 KB Output is correct
2 Correct 109 ms 1708 KB Output is correct
3 Correct 104 ms 1740 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 1676 KB Output is correct
2 Correct 119 ms 1832 KB Output is correct
3 Correct 105 ms 1720 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1740 KB Output is correct
2 Correct 123 ms 1796 KB Output is correct
3 Correct 112 ms 1836 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 1824 KB Output is correct
2 Correct 118 ms 1768 KB Output is correct
3 Correct 113 ms 1820 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 1740 KB Output is correct
2 Correct 131 ms 1860 KB Output is correct
3 Correct 114 ms 1740 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1740 KB Output is correct
2 Correct 121 ms 1832 KB Output is correct
3 Correct 117 ms 1836 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1740 KB Output is correct
2 Correct 119 ms 1836 KB Output is correct
3 Correct 115 ms 1836 KB Output is correct