oj.uz

Submission #410961

# Submission time Handle Problem Language Result Execution time Memory
410961 2021-05-24T01:42:37 Z jjang36524 Akvizna (COCI19_akvizna) C++14
120 / 130
 196 ms 1864 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++)
	{
		s = max(1LL, s - 10);
		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("%.10f", dp[N]+M*s);
}

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
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 #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 4 ms 352 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 5 ms 332 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 7 ms 332 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 6 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 #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 1740 KB Output is correct
2 Correct 136 ms 1740 KB Output is correct
3 Correct 115 ms 1708 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1744 KB Output is correct
2 Correct 133 ms 1740 KB Output is correct
3 Correct 121 ms 1768 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 1740 KB Output is correct
2 Correct 140 ms 1740 KB Output is correct
3 Correct 127 ms 1828 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 1740 KB Output is correct
2 Correct 141 ms 1808 KB Output is correct
3 Correct 121 ms 1756 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 1740 KB Output is correct
2 Correct 138 ms 1836 KB Output is correct
3 Correct 120 ms 1748 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1844 KB Output is correct
2 Correct 139 ms 1708 KB Output is correct
3 Correct 126 ms 1864 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 1812 KB Output is correct
2 Correct 123 ms 1704 KB Output is correct
3 Correct 120 ms 1704 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 1740 KB Output is correct
2 Correct 134 ms 1740 KB Output is correct
3 Correct 117 ms 1720 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 1828 KB Output is correct
2 Correct 140 ms 1740 KB Output is correct
3 Correct 128 ms 1832 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1740 KB Output is correct
2 Correct 134 ms 1740 KB Output is correct
3 Correct 125 ms 1740 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1844 KB Output is correct
2 Correct 145 ms 1740 KB Output is correct
3 Correct 128 ms 1844 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 1840 KB Output is correct
2 Correct 137 ms 1740 KB Output is correct
3 Correct 128 ms 1844 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1852 KB Output is correct
2 Correct 136 ms 1740 KB Output is correct
3 Correct 128 ms 1848 KB Output is correct