Cod sursa(job #2036971)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 11 octombrie 2017 15:39:16
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <deque>
#define N 50005
#define abs(x) x>0 ? x: -x

using namespace std;

int s[N], a[N], n, k;
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++)
//        printf("%d ", s[i]);

    for(int i=1;i<k;i++)
    {
        while(!mini.empty() && s[mini.back()]>s[i])
            mini.pop_back();
        mini.push_back(i);
        while(!maxi.empty() && s[maxi.back()]<s[i])
            maxi.pop_back();
        maxi.push_back(i);
    }

    for(int i=k;i<=n;i++)
    {
        while(!mini.empty() && s[mini.back()]>s[i])
            mini.pop_back();
        mini.push_back(i);

        while(!maxi.empty() && s[maxi.back()]<s[i])
            maxi.pop_back();
        maxi.push_back(i);
    }

    int pozmin=mini.front();
    int pozmax=maxi.front();
    printf("%d %d %d", pozmin+1, pozmax, s[pozmax]-s[pozmin]);
    return 0;
}