CF - Books

Author: Benjamin Qi


Official Editorial (Russian)

(Translated)

It is easiest to use the method of two pointers. The left pointer means the beginning of the segment of books to read, the right one - the end. When moving the left pointer one unit to the right, the right pointer should be repeatedly moved to the right as long as the sum of all aia_i within the segment is less than or equal to tt. This way, we can find for each possible left end the rightmost possible right end. The answer to the problem is the maximum length over all possible left ends.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using pi = pair<int, int>;
using pl = pair<ll, ll>;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!