oj.uz

Submission #410957

# Submission time Handle Problem Language Result Execution time Memory
410957 2021-05-24T01:34:14 Z jjang36524 Akvizna (COCI19_akvizna) C++14
120 / 130
 307 ms 1992 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 -= 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 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 1 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 320 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 8 ms 368 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 5 ms 368 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 368 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 1752 KB Output is correct
2 Correct 197 ms 1808 KB Output is correct
3 Correct 172 ms 1732 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 1760 KB Output is correct
2 Correct 191 ms 1740 KB Output is correct
3 Correct 181 ms 1740 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 1740 KB Output is correct
2 Correct 198 ms 1864 KB Output is correct
3 Correct 189 ms 1868 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1804 KB Output is correct
2 Correct 197 ms 1832 KB Output is correct
3 Correct 179 ms 1724 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 1760 KB Output is correct
2 Correct 198 ms 1856 KB Output is correct
3 Correct 181 ms 1768 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 1868 KB Output is correct
2 Correct 196 ms 1796 KB Output is correct
3 Correct 182 ms 1776 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1820 KB Output is correct
2 Correct 181 ms 1728 KB Output is correct
3 Correct 174 ms 1748 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 1764 KB Output is correct
2 Correct 198 ms 1868 KB Output is correct
3 Correct 174 ms 1756 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 1868 KB Output is correct
2 Correct 201 ms 1844 KB Output is correct
3 Correct 192 ms 1868 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 1852 KB Output is correct
2 Correct 190 ms 1740 KB Output is correct
3 Correct 188 ms 1868 KB Output is correct

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 1868 KB Output is correct
2 Correct 208 ms 1868 KB Output is correct
3 Correct 192 ms 1872 KB Output is correct

Subtask #25
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 1864 KB Output is correct
2 Correct 202 ms 1868 KB Output is correct
3 Correct 191 ms 1868 KB Output is correct

Subtask #26
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 1868 KB Output is correct
2 Correct 200 ms 1992 KB Output is correct
3 Correct 193 ms 1868 KB Output is correct