Cod sursa(job #2038170)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 13 octombrie 2017 14:01:10
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#include <deque>
#define N 50005

using namespace std;

int s[N], a[N], n, k, maxim, pmax, pmin;
deque <int> mini, maxi;

int main()
{
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);

    scanf("%d %d\n", &n, &k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d ", &a[i]);
        s[i]=s[i-1]+a[i];
    }

    for(int i=1;i<=n;i++)
    {
        while(!maxi.empty() && s[maxi.back()]<s[i])
            maxi.pop_back();
        maxi.push_back(i);
        while(!mini.empty() && s[mini.back()]>s[i])
            mini.pop_back();
        mini.push_back(i);
        if(i>=k && maxim<s[maxi.front()]-s[mini.front()])
        {
            maxim=s[maxi.front()]-s[mini.front()];
            pmax=maxi.front();
            pmin=mini.front();
        }
    }
    printf("%d %d %d", pmin+1, pmax, maxim);
    return 0;
}