Submission #410571

#	Time	Username	Problem	Language	Result	Execution time	Memory
410571		koioi.org-namnamseo	새로운 문제 (COCI19_akvizna)	C++17	130 / 130	166 ms	1868 KiB

Main

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5
• Subtask 24: 5 / 5
• Subtask 25: 5 / 5
• Subtask 26: 5 / 5