Ta gọi ~f_i = a_1 + a_2 + ... + a_i~.

Vì phần tử nhỏ nhất trong dãy con cần tìm phải có giá trị từ ~x~ đến ~y~ nên các phần tử trong dãy đều phải lớn hơn hoặc bằng ~x~.

Vậy các số trong dãy bài cho bé hơn ~x~ ta sẽ coi như không xét số đó, dãy bài cho ban đầu sẽ được chia thành nhiều dãy con.

Ta sẽ xét từng dãy con, gọi hai đầu mút của dãy con là ~l~ và ~r~.

Với từng ~i~ ~(l \le i \le r)~, ta cần tìm ~j~ sao cho ~a_j \le y~, ~j \le i~ và ~j~ lớn nhất. Ta thấy nếu ~i~ tăng thì ~j~ cũng sẽ tăng nên để tìm được ~j~, từ đó ta sẽ dùng kĩ thuật hai con trỏ.

Để tổng của dãy con cần tìm lớn nhất thì ta cần tìm ~x~ sao cho ~l - 1 \le x < j~ và ~f_x~ nhỏ nhất. Ta tìm được ~x~ thông qua ~j~

Kết quả chính là ~f_i - f_x~ lớn nhất.

Đô phức tạp: ~O(n)~

Code mẫu

#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define fid(i,a,b) for(int i=a;i>=b;i--)
#define getbit(x,i) ((x>>i)&1)
#define pii pair<int,int>
#define ll long long
#define TunaNgoo "main"
#define maxn 5000005
using namespace std;
int n, x, y, a[maxn];
ll res = -1e18, l, r, f[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen(TunaNgoo".inp", "r", stdin);
    freopen(TunaNgoo".out", "w", stdout);
    #endif // ONLINE_JUDGE
    cin >> n;
    cin >> x >> y;
    fi(i, 1, n) cin >> a[i];
    int v, vt, j;
    fi(u, 1, n)
    if(a[u] >= x)
    {
        v = u;
        while(v <= n && a[v] >= x) v++;
        v--;
        f[u - 1] = 0;
        vt = u - 1;
        j = u - 1;
        fi(i, u, v)
        {
            f[i] = f[i - 1] + a[i];
            if(a[i] >= x && a[i] <= y)
            {
                while(j < i)
                {
                    if(f[vt] > f[j]) vt = j;
                    j++;
                }
            }
            if(j >= u && res < f[i] - f[vt])
            {
                res = f[i] - f[vt];
                l = vt + 1;
                r = i;
            }
        }
        u = v;
    }
    cout << res << '\n' << l << " " << r;
}