oj.uz

Submission #410959

# Submission time Handle Problem Language Result Execution time Memory
410959 2021-05-24T01:36:28 Z jjang36524 Akvizna (COCI19_akvizna) C++14
125 / 130
 48 ms 1844 KB 
#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++)
	{
		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()
{
	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;
	}
	printf("%.15f", dp[N]+M*s);
}

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 3 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 3 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 340 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 332 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 45 ms 1740 KB Output is correct
2 Correct 42 ms 1780 KB Output is correct
3 Correct 40 ms 1716 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1740 KB Output is correct
2 Correct 43 ms 1740 KB Output is correct
3 Correct 42 ms 1788 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1740 KB Output is correct
2 Correct 47 ms 1840 KB Output is correct
3 Correct 44 ms 1836 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1800 KB Output is correct
2 Correct 42 ms 1740 KB Output is correct
3 Correct 40 ms 1760 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1740 KB Output is correct
2 Correct 47 ms 1740 KB Output is correct
3 Correct 42 ms 1740 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1740 KB Output is correct
2 Correct 41 ms 1740 KB Output is correct
3 Correct 43 ms 1756 KB Output is correct

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1740 KB Output is correct
2 Correct 43 ms 1740 KB Output is correct
3 Correct 41 ms 1612 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1828 KB Output is correct
2 Correct 42 ms 1740 KB Output is correct
3 Correct 43 ms 1740 KB Output is correct

Subtask #23
5.0 / 5.0

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

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1740 KB Output is correct
2 Correct 44 ms 1740 KB Output is correct
3 Correct 45 ms 1840 KB Output is correct

Subtask #25
5.0 / 5.0

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

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1740 KB Output is correct
2 Correct 44 ms 1740 KB Output is correct
3 Correct 46 ms 1844 KB Output is correct