Cod sursa(job #1818249)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 28 noiembrie 2016 22:28:04
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include <deque>
using namespace std;

int v[50005], sp[50005];
deque <int> dq;

int main()
{
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);
    int ans = -1000000005, n, lmin, st, dr;
    scanf("%d %d", &n, &lmin);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &v[i]);
        sp[i] = sp[i - 1] + v[i];

        if (i >= lmin)
        {
            while (!dq.empty() && sp[i - lmin] < sp[dq.back()])
                dq.pop_back();
            dq.push_back(i - lmin);

            if (!dq.empty() && sp[i] - sp[dq.front()] > ans)
                ans = sp[i] - sp[dq.front()], dr = i, st = dq.front() + 1;
        }
    }
    printf("%d %d %d\n", st, dr, ans);
    return 0;
}