[알고스팟][C++] FESTIVAL: 록 페스티벌

문제 링크: https://algospot.com/judge/problem/read/FESTIVAL

 

종만북 맨 처음에 있는 문제입니다.

누적합을 쓰면 효율적입니다.

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		int N, L;
		cin >> N >> L;

		vector<int> c_sum(N+1);	// 누적합: 0, ...
		for (int i = 1; i <= N; ++i) {
			cin >> c_sum[i];
			c_sum[i] += c_sum[i - 1];
		}

		double min_avg = 1e9;
		for (int width = N; width >= L; --width) {
			for (int i = 0; i < N - width + 1; ++i) {
				min_avg = min(min_avg, (c_sum[i+width] - c_sum[i]) / (double)width);
			}
		}

		cout << setprecision(8) << fixed << min_avg << '\n';
	}
	
	return 0;
}

0번 인덱스에는 0을 넣어 아무것도 넣지 않았을 때의 값을 저장해 썼습니다.