Competitive Programming Solutions

279B - Books

29 Dec 2020 — Tags: two_pointers,brute_force — URL

We need to find a pair of indices [l, r] such that the sum of the book times in this interval is less than $t$ and is maximal.

We may fix the left border, $l$, and use binary search or a two pointers approach to find $r$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a, int t)
{
    int n = (int)(a).size(), r = 0, ans = 0;
    vi pa(n);
    partial_sum(begin(a), end(a), begin(pa));
    auto sum = [pa](int l, int r) { return pa[r] - (l == 0 ? 0 : pa[l - 1]); };
    for (int l = 0; l < n; ++l)
    {
        while (r < n and sum(l, r) <= t)
            ++r;
        ans = max(ans, r - l);
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, t;
    cin >> n >> t;
    vi a(n);
    for (auto &x : a)
        cin >> x;
    cout << solve(a, t) << endl;
    return 0;
}

Related posts