Submission #410957

#	Time	Username	Problem	Language	Result	Execution time	Memory
410957		jjang36524	새로운 문제 (COCI19_akvizna)	C++14	120 / 130	307 ms	1992 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
double dp[200100];
int cou[200100];
int N;
int f(double c)
{
	int s = 1;
	int i;
	dp[0] = 0;
	for (i = 1; i <= N; i++)
	{
		s -= 20;
		s = max(1LL, s);
		dp[i] = (double)s / i;
		
		dp[i] += dp[i-s]-c;
		while (s < i)
		{
			double newdp = (double)(s + 1) / i + dp[i - s - 1] - c;
			if (newdp > dp[i])
			{
				dp[i] = newdp;
				s++;
			}
			else
				break;
		}
		cou[i] = cou[i - s] + 1;
	}
	return cou[N];
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int  M;
	cin >> N >> M;
	double s = 0, e = 10;
	int i;
	for (i = 0; i < 60; i++)
	{
		if (s >= e)
			break;
		double m = (s + e) / 2;
		if (f(m) > M)
			s = m;
		else
			e = m;
	}
	cout.precision(15);
	cout << dp[N]+M*s;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 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