Official Analysis (Java)

Explanation

To find the lowest maximum haybale spiciness, we find the maximum spiciness of a sliding window meeting the minimum flavor sum requirement. We use a sliding window because the haybales must be consecutive.

This is achieved by expanding our window to the right until the flavor sum requirement is met, then finding the largest element in our window.

It is best to not expand our window after the flavor sum requirement is met because it potentially will result in adding a haybale with a large spiciness, making the maximum haybale spiciness larger than it should be.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

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

int main() {
	ifstream read("hayfeast.in");

	int n;
	long long m;
	read >> n >> m;
	vector<pair<int, int>> haybales(n);