oj.uz

Submission #410610

# Submission time Handle Problem Language Result Execution time Memory
410610 2021-05-23T07:14:07 Z Namnamseo Akvizna (COCI19_akvizna) C++17
130 / 130
 168 ms 1860 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 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 #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 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 4 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 5 ms 348 KB Output is correct
3 Correct 3 ms 348 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 332 KB Output is correct
3 Correct 3 ms 340 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 448 KB Output is correct

Subtask #9
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 3 ms 352 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 156 ms 1740 KB Output is correct
2 Correct 120 ms 1772 KB Output is correct
3 Correct 106 ms 1692 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1740 KB Output is correct
2 Correct 118 ms 1720 KB Output is correct
3 Correct 114 ms 1776 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 1740 KB Output is correct
2 Correct 126 ms 1840 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 149 ms 1788 KB Output is correct
2 Correct 121 ms 1740 KB Output is correct
3 Correct 111 ms 1740 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1860 KB Output is correct
2 Correct 124 ms 1832 KB Output is correct
3 Correct 108 ms 1752 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 125 ms 1792 KB Output is correct
3 Correct 110 ms 1756 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 1740 KB Output is correct
2 Correct 112 ms 1612 KB Output is correct
3 Correct 110 ms 1740 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 1748 KB Output is correct
2 Correct 130 ms 1740 KB Output is correct
3 Correct 103 ms 1712 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1740 KB Output is correct
2 Correct 126 ms 1860 KB Output is correct
3 Correct 113 ms 1832 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 1820 KB Output is correct
2 Correct 119 ms 1740 KB Output is correct
3 Correct 117 ms 1824 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 1840 KB Output is correct
2 Correct 127 ms 1740 KB Output is correct
3 Correct 113 ms 1832 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1836 KB Output is correct
2 Correct 123 ms 1832 KB Output is correct
3 Correct 114 ms 1832 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 1836 KB Output is correct
2 Correct 122 ms 1836 KB Output is correct
3 Correct 128 ms 1832 KB Output is correct