[Codeforce 1003C] C. Intense Heat

https://codeforces.com/problemset/problem/1003/C

Problem - 1003C - Codeforces

 

알고리즘연습 2024.03.15

<유형>

다이나믹 프로그래밍

프리픽스 썸 (Prefix Sum)

 

<배운점 정리>

1. not less than k

= k 이상

 

2. k 이상의 연속적인 날들의 평균치 였으므로 k개의 연속적인 날만 확인하면 안되고,

최대 n개의 날들의 평균치까지 함께 고려해야 함.

 

3. cout.precision(15); 를 먼저 선언하면

cout할 때 소수점 이하 15자리까지 출력이 가능하다.

 

아래는 정답 코드

---

#include <iostream>

using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;

	long long A[5005];
	long long P[5005];

	A[0] = 0;
	long long a;

	P[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		A[i] = a;	
		P[i] = P[i - 1] + A[i];
	}

	double ans = 0.0;

	for (int j = k; j <= n; j++)
	{
		for (int i = 1; i <= n - j + 1; i++)
		{
			ans = max(ans, (double)(P[i + j - 1] - P[i-1])/(double)j);
		}		
	}

	cout.precision(15);
	cout << ans;
}